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$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$n em notação assintótica, você poderia dizer que esse algoritmo é executado num tempo $\Theta(n^0)$\Theta, left parenthesis, n, start superscript, 0, end superscript, right parenthesis. Por quê? Porque $n ^ 0 = 1$n, start superscript, 0, end superscript, equals, 1, e o tempo de execução do algoritmo está contido em um fator constante de 1. Na prática, não escrevemos $\Theta(n^0)$\Theta, left parenthesis, n, start superscript, 0, end superscript, right parenthesis, em vez disso, escrevemos $\Theta(1)$\Theta, left parenthesis, 1, right parenthesis.

Agora suponha que um algoritmo levou um tempo de $\Theta(\log_{10} n)$\Theta, left parenthesis, log, start base, 10, end base, n, right parenthesis para ser executado. Você também pode dizer que ele levou um tempo de $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis. 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$a, $b$b e $n$n. Portanto, se $a$a e $b$b são constantes, então $\log_a n$log, start base, a, end base, n e $\log_b$log, start base, b, end base n diferem apenas por um fator de $\log_b a$log, start base, b, end base, 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 é $\Theta(\log_a n)$\Theta, left parenthesis, log, start base, a, end base, n, right parenthesis para qualquer constante positiva $a$a. Por quê? O número de chutes é, no máximo, $\log_2 n + 1$log, start base, 2, end base, n, plus, 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 $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis 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$a e $b$b são constantes e $a < b$a, is less than, b, então o tempo de execução $\Theta(n^a)$\Theta, left parenthesis, n, start superscript, a, end superscript, right parenthesis cresce mais lentamente do que um tempo de execução $\Theta(n^b)$\Theta, left parenthesis, n, start superscript, b, end superscript, right parenthesis. Por exemplo, o tempo de execução $\Theta(n)$\Theta, left parenthesis, n, right parenthesis, que é $\Theta(n^1)$\Theta, left parenthesis, n, start superscript, 1, end superscript, right parenthesis, cresce mais lentamente do que um tempo de execução $\Theta(n^2)$\Theta, left parenthesis, n, squared, right parenthesis. Os expoentes também não têm de ser inteiros. Por exemplo, o tempo de execução de $\Theta(n^2)$\Theta, left parenthesis, n, squared, right parenthesis cresce mais lentamente do que um tempo de execução $\Theta(n^2 \sqrt{n})$\Theta, left parenthesis, n, squared, square root of, n, end square root, right parenthesis, que é $\Theta(n^{2,5})$\Theta, left parenthesis, n, start superscript, 2, comma, 5, end superscript, right parenthesis.

O gráfico a seguir compara o crescimento de $n$n, $n^2$n, squared e $n^{2.5}$n, start superscript, 2, point, 5, end superscript:

Logaritmos crescem mais lentamente do que os polinômios. Ou seja, $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis cresce de forma mais lenta que $\Theta(n^a)$\Theta, left parenthesis, n, start superscript, a, end superscript, right parenthesis para qualquer constante positiva $a$a. Mas uma vez que o valor de $\log_2 n$log, start base, 2, end base, n cresce quando $n$n cresce, $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis possui um crescimento mais rápido que $\Theta(1)$\Theta, left parenthesis, 1, right parenthesis.

O gráfico a seguir compara o crescimento de $1$1, $n$n e $\log_2 n$log, start base, 2, end base, 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$a, start superscript, n, end superscript, em que $a > 1$a, is greater than, 1, cresce mais rápido do que qualquer função polinomial $n^b$n, start superscript, b, end superscript, em que $b$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.