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$‍, leve $6n^2+100n+300$‍ instruções de máquina. O termo $6n^2$‍ torna-se maior do que os outros termos, $100n+300$‍, uma vez que $n$‍ torna-se grande o suficiente,  20  neste caso. Abaixo temos um gráfico que mostra os valores de $6n^2$‍ e $100n+300$‍ para valores de $n$‍ variando entre 0 e 100:

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

O valor de $n$‍ para o qual $0,6n^2$‍ se torna maior que $1000n+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 $\mathrm{\Theta }$‍, notação O, notação $\mathrm{\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.