Notação assintótica

Até agora, analisamos a busca linear e a busca binária contando o número máximo de tentativas necessárias. Mas o que realmente queremos saber é quanto tempo esses algoritmos demoram. Estamos interessados no tempo, não só nas suposições. Os tempos de execução da busca linear e da busca binária incluem o tempo necessário para gerar e checar palpites, mas algoritmos não se resumem a isso.

O tempo de execução de um algoritmo depende do quão demorado é para um computador executar as linhas de código do algoritmo e isto depende da velocidade deste computador, da linguagem de programação, e do compilador que traduziu o programa da linguagem de programação para o código que executa diretamente no computador, entre outros fatores.

Vamos pensar com mais cuidado no tempo de execução de um algoritmo. Podemos usar a combinação de duas ideias. Primeiro, precisamos determinar quanto tempo o algoritmo leva em termos do tamanho da entrada. Esta ideia parece intuitiva, não é mesmo? Já vimos que o máximo de tentativas necessárias em busca linear e em busca binária aumenta conforme aumenta o tamanho do array de candidatos. Ou pense sobre um GPS. Se ele conhecesse apenas o sistema de rodovias principais, e não todas as pequenas estradas secundárias, ele deveria ser capaz de buscar rotas mais rapidamente, certo? So we think about the running time of the algorithm as a function of the size of its input.

A segunda ideia é que precisamos focar em quão rápido uma função cresce com o tamanho da entrada. Chamamos isso de taxa de crescimento do tempo de execução. Para manter as coisas tratáveis, precisamos simplificar a função até evidenciar a parte mais importante e deixar de lado as menos importantes. Por exemplo, suponha que um algoritmo, sendo executado com uma entrada de tamanho $n$n, leve $6n^2 + 100n + 300$6, n, squared, plus, 100, n, plus, 300 instruções de máquina. O termo $6n^2$6, n, squared torna-se maior do que os outros termos, $100n + 300$100, n, plus, 300, uma vez que $n$n torna-se grande o suficiente,  20  neste caso. Abaixo temos um gráfico que mostra os valores de $6n^2$6, n, squared e $100n + 300$100, n, plus, 300 para valores de $n$n variando entre 0 e 100:

Podemos dizer que este algoritmo cresce a uma taxa $n^2$n, squared, deixando de fora o coeficiente 6 e os termos restantes $100n + 300$100, n, plus, 300. Não é realmente importante que coeficientes usamos, já que o tempo de execução é $an^2 + bn + c$a, n, squared, plus, b, n, plus, c, para alguns números $a > 0$a, is greater than, 0, $b$b, e $c$c, sempre haverá um valor de $n$n para o qual $an^2$a, n, squared é maior que $bn + c$b, n, plus, c, e essa diferença aumenta juntamente com $n$n. Por exemplo, aqui está um gráfico mostrando os valores de $0{,}6n^2$0, comma, 6, n, squared e $1000n + 3000$1000, n, plus, 3000  de modo que reduzimos o coeficiente de $n^2$n, squared por um fator de 10 e aumentamos as outras duas constantes por um fator de 10:

O valor de $n$n para o qual $0,6n^2$0, comma, 6, n, squared se torna maior que $1000n + 3000$1000, n, plus, 3000 aumentou, mas sempre haverá um ponto de cruzamento, independentemente das constantes.

Descartando os termos menos significativos e os coeficientes constantes, podemos nos concentrar na parte importante do tempo de execução de um algoritmo — sua taxa de crescimento — sem sermos atrapalhados por detalhes que complicam sua compreensão. Quando descartamos os coeficientes constantes e os termos menos significativos, usamos notação assintótica. Vamos estudar suas três formas: notação $\Theta$\Theta, notação O, notação $\Omega$\Omega.

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