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?

  • Avatar piceratops seed style do usuário Vinicius da Silva
    o que o "n" e o "a" representam ??
    (11 votos)
    Avatar Default Khan Academy avatar do usuário
  • Avatar piceratops ultimate style do usuário Luiza Spínola
    Boa tarde,
    Eu iniciei os estudos em "Ciência da Computação" por algoritmos, mas ao chegar nessa parte de notação assintótica eu me perdi completamente.
    Estou estudando matemática pelo próprio khanacademy, mas ainda não cheguei em nenhuma parte parecida com Notação Big-θ ou big-Θ.

    Tem alguma parte anterior por onde deveria ter começado? Desde já agradeço.
    (10 votos)
    Avatar Default Khan Academy avatar do usuário
    • Avatar blobby green style do usuário Vander James
      Neste contexto de análise de algoritmos, a constante 'a' representa o número de instruções a serem realizadas. A variável 'n' representa o número de dados de entrada a serem processados.
      (5 votos)
  • Avatar blobby green style do usuário Levi Veras
    Quando descartamos os coeficientes constantes e os termos menos significativos, usamos notação assintótica.
    (4 votos)
    Avatar Default Khan Academy avatar do usuário
  • Avatar duskpin seedling style do usuário Vinicius Gregorine
    só um comentário: engraçado aqui os comentários serem de 2 anos para trás.
    (3 votos)
    Avatar Default Khan Academy avatar do usuário
  • Avatar blobby green style do usuário maria noeli polachini
    O que é notação assintótica?
    (3 votos)
    Avatar Default Khan Academy avatar do usuário
  • Avatar blobby green style do usuário jarbson_barbosa
    olá porém se em uma função se for considerado apenas a aplicação em um intervalo inferior ao ponto de cruzamento, a parte mais significativa será a parte anteriormente desprezada.
    (1 voto)
    Avatar Default Khan Academy avatar do usuário
  • Avatar blobby green style do usuário thainaramiranda676
    no final disponibilizam certificado?
    (1 voto)
    Avatar Default Khan Academy avatar do usuário
Você entende inglês? Clique aqui para ver mais debates na versão em inglês do site da Khan Academy.