Notações Assintóticas

Você sabe o que significa dizer que a função de complexidade de um algoritmo pertence a classe O(n)? Nesse post você irá compreender o que notações desse tipo significam e qual a importância em determinar a classe da função de complexidade de um algoritmo.

De forma simplista, algoritmo é um procedimento que transforma algum valor, ou conjunto de valores (entrada) e produz algum valor, ou conjunto de valores (saída). Sua função de complexidade geralmente depende majoritariamente do tamanho da entrada que será processada pelo algoritmo, de forma que um algoritmo que demora 10 minutos para realizar algum procedimento sobre uma determinada entrada, é mais eficiente que outro que demora 10 horas para realizar o mesmo procedimento sobre a mesma entrada, considerando-se as mesmas condições.

Para que seja mais fácil classificar algoritmos quanto ao seu tempo de execução quando estes trabalham com uma quantidade de valores muito grande, algoritmos são divididos em classes de complexidade diferentes.

É importante destacar que quando se fala em tempo de execução, não estamos de fato calculando o tempo que um algoritmo demora para produzir uma saída a partir de uma entrada de tamanho n, mas sim a quantidade de instruções que este algoritmo necessita para produzir essa saída.

Notação Big-O (lê-se big o): Dadas duas funções assintoticamente não negativas f e g, dizemos que f está na ordem de g e escrevemos f ∈ O(g) se f(n) ≤ c.g(n) para algum c positivo e um n suficientemente grande. Ou seja, quando afirmamos que um algoritmo é da ordem de O(n²) por exemplo, estamos querendo dizer que a ordem de instruções que o algoritmo precisa realizar para gerar uma saída, a partir de uma entrada de tamanho n, é de no máximo n².

Notação Big-Ω (lê-se big ômega): Dadas duas funções assintoticamente não negativas f e g, dizemos que f está na ordem de g e escrevemos f ∈ Ω(g) se c.g(n) ≤ f(n) para algum c positivo e um n suficientemente grande. Ou seja, quando afirmamos que um algoritmo é da ordem de Ω(n³) por exemplo, estamos querendo dizer que a ordem de instruções que o algoritmo precisa realizar para gerar uma saída, a partir de uma entrada de tamanho n, é de no mínimo n³.   

Para saber um pouco mais sobre notações assintóticas e análise assintótica de algoritmos, você pode clicar aqui.

Por,

Wesley Santos - Integrante do PET Computação