Funções em notação assintótica

Quando usamos a notação assintótica para expressar a taxa de crescimento do tempo de execução de um algoritmo, em termos do tamanho de entrada $n$‍, é bom ter algumas coisas em mente.

Vamos começar com algo fácil. Suponha que um algoritmo demorou uma quantidade constante de tempo para ser executado, independentemente do tamanho da entrada. Por exemplo, se você recebeu um array que já estava em ordem crescente e você tinha que localizar o menor elemento, a execução levaria um tempo constante, já que o elemento mínimo deve estar no índice 0. Como gostamos de usar funções de $n$‍ em notação assintótica, você poderia dizer que esse algoritmo é executado num tempo $\mathrm{\Theta }(n^0)$‍. Por quê? Porque $n^0=1$‍, e o tempo de execução do algoritmo está contido em um fator constante de 1. Na prática, não escrevemos $\mathrm{\Theta }(n^0)$‍, em vez disso, escrevemos $\mathrm{\Theta }(1)$‍.

Agora suponha que um algoritmo levou um tempo de $\mathrm{\Theta }({\log }_{10}n)$‍ para ser executado. Você também pode dizer que ele levou um tempo de $\mathrm{\Theta }({\log }_{2}n)$‍. Sempre que a base do logaritmo for constante, não importa em que base usamos a notação assintótica. Por que não? Porque existe uma fórmula matemática que diz:

para todos os números positivos $a$‍, $b$‍ e $n$‍. Portanto, se $a$‍ e $b$‍ são constantes, então ${\log }_{a}n$‍ e ${\log }_b$‍ n diferem apenas por um fator de ${\log }_{b}a$‍, e isso é um fator constante que podemos ignorar em notação assintótica.

Portanto, podemos dizer que o pior cenário do tempo de execução de uma busca binária é $\mathrm{\Theta }({\log }_{a}n)$‍ para qualquer constante positiva $a$‍. Por quê? O número de chutes é, no máximo, ${\log }_{2}n+1$‍, gerar e testar cada chute leva um tempo constante, e configurar e retornar o valor também leva um tempo constante. No entanto, por uma questão de prática, frequentemente escrevemos que a busca binária leva $\mathrm{\Theta }({\log }_{2}n)$‍ porque cientistas da computação gostam de pensar em potências de 2.

Há uma ordem para as funções que vemos frequentemente quando analisamos algoritmos usando notação assintótica. Se $a$‍ e $b$‍ são constantes e $a<b$‍, então o tempo de execução $\mathrm{\Theta }(n^a)$‍ cresce mais lentamente do que um tempo de execução $\mathrm{\Theta }(n^b)$‍. Por exemplo, o tempo de execução $\mathrm{\Theta }(n)$‍, que é $\mathrm{\Theta }(n^1)$‍, cresce mais lentamente do que um tempo de execução $\mathrm{\Theta }(n^2)$‍. Os expoentes também não têm de ser inteiros. Por exemplo, o tempo de execução de $\mathrm{\Theta }(n^2)$‍ cresce mais lentamente do que um tempo de execução $\mathrm{\Theta }(n^2\sqrt{n})$‍, que é $\mathrm{\Theta }(n^{2,5})$‍.

O gráfico a seguir compara o crescimento de $n$‍, $n^2$‍ e $n^{2.5}$‍:

Logaritmos crescem mais lentamente do que os polinômios. Ou seja, $\mathrm{\Theta }({\log }_{2}n)$‍ cresce de forma mais lenta que $\mathrm{\Theta }(n^a)$‍ para qualquer constante positiva $a$‍. Mas uma vez que o valor de ${\log }_{2}n$‍ cresce quando $n$‍ cresce, $\mathrm{\Theta }({\log }_{2}n)$‍ possui um crescimento mais rápido que $\mathrm{\Theta }(1)$‍.

O gráfico a seguir compara o crescimento de $1$‍, $n$‍ e ${\log }_{2}n$‍:

Aqui está uma lista de funções em noção assintótica que encontramos muitas vezes quando analisamos algoritmos, listadas do crescimento mais lento para o crescimento mais rápido.

Observe que uma função exponencial $a^n$‍, em que $a>1$‍, cresce mais rápido do que qualquer função polinomial $n^b$‍, em que $b$‍ é qualquer constante.

A lista acima não é exaustiva, existem muitas funções com tempos de execução que não estão listadas aqui. Você vai encontrar com algumas delas em sua jornada na ciência da computação.

Este conteúdo é uma colaboração entre os professores de ciência da computação da Universidade de Dartmouth, Thomas Cormen e Devin Balkcom, juntamente com a equipe do currículo de computação da Khan Academy. O conteúdo é licenciado CC-BY-NC-SA.