If you're seeing this message, it means we're having trouble loading external resources on our website.

Se você está atrás de um filtro da Web, certifique-se que os domínios *.kastatic.org e *.kasandbox.org estão desbloqueados.

Conteúdo principal

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 6, n, squared, plus, 100, n, plus, 300 instruções de máquina. O termo 6, n, squared torna-se maior do que os outros termos, 100, n, plus, 300, uma vez que n torna-se grande o suficiente,  20  neste caso. Abaixo temos um gráfico que mostra os valores de 6, n, squared e 100, n, plus, 300 para valores de n variando entre 0 e 100:
Podemos dizer que este algoritmo cresce a uma taxa n, squared, deixando de fora o coeficiente 6 e os termos restantes 100, n, plus, 300. Não é realmente importante que coeficientes usamos, já que o tempo de execução é a, n, squared, plus, b, n, plus, c, para alguns números a, is greater than, 0, b, e c, sempre haverá um valor de n para o qual a, n, squared é maior que b, n, plus, c, e essa diferença aumenta juntamente com n. Por exemplo, aqui está um gráfico mostrando os valores de 0, comma, 6, n, squared e 1000, n, plus, 3000  de modo que reduzimos o coeficiente de n, squared por um fator de 10 e aumentamos as outras duas constantes por um fator de 10:
O valor de n para o qual 0, comma, 6, n, squared se torna maior que 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, notação O, notação \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.

Quer participar da conversa?

Você entende inglês? Clique aqui para ver mais debates na versão em inglês do site da Khan Academy.