Conteúdo principal
Curso: Computer science theory > Unidade 1
Lição 3: Notação assintóticaNotação Big-θ (Grande-Theta)
Vamos ver uma implementação simples da busca linear:
var doLinearSearch = function(array, targetValue) {
for (var guess = 0; guess < array.length; guess++) {
if (array[guess] === targetValue) {
return guess; // Encontrou!
}
}
return -1; // Não encontrou
};Vamos indicar o tamanho do array (
array.length) como A cada iteração do laço, há diversas coisas a serem feitas:
- comparar a variável
guesscomarray.length - comparar
array[guess]comtargetValue - possivelmente retornar o valor da variável
guess - incrementar a variável
guess.
Cada uma dessas pequenas computações são executadas em um tempo constante a cada iteração. Se o laço "for" se repete
Esse código possui uma pequena sobrecarga extra, para configurar o laço "for" (o que inclui inicializar o valor de
guess como 0) e possivelmente retornar -1 no final. Vamos chamar o tempo dessa sobrecarga de Como dissemos, o fator constante
Quando dizemos que um tempo de execução em particular é
Para valores pequenos de
Não estamos restritos a apenas
Uma vez que o
Na prática, simplesmente descartamos fatores constantes e termos de ordem inferior. Outra vantagem de usar a notação Θ é que não temos que nos preocupar com quais unidades de tempo estamos usando. Por exemplo, suponha que você tenha calculado que um tempo de execução é de
Quando usamos a notação big-Θ estamos dizendo que temos um limite assintoticamente restrito no tempo de execução. "Assintoticamente" porque ele importa apenas para valores grandes de
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.
Quer participar da conversa?
Para fins de escrita,O = Theta;O tem valor numérico ou é só unidade mesmo?(3 votos)
Theta é o conjunto de todas as funções limitadas pelas duas constantes k1 e k2 (0 <= k1 <= k2) a partir de um certo n (veja a linha pontilhada no último gráfico). Assim, por exemplo, quando dizemos que o tempo de um algoritmo dado por uma função g(n) = n^2 + n é Theta(n^2), isto é, g(n) = Theta(n^2), no fundo estamos dizendo que a função g(n) = n^2 + n pertence ao conjunto das funções g(n) que estão no intervalo k1.n^2 <= g(n) <= k2.n^2, a partir de um certo valor constante de n (linha pontilhada).(16 votos)
Há um pequeno trecho do texto que continua em inglês, tem alguma forma de corrigir? Grato(7 votos)
Como é definido o valor de k1 e k2?(7 votos)- olha, talvez o problrma seja eu, mas o texto ficou bem cansativo, so depois de analisar o gráfico consegui entender.
se fosse depender do texto ia ser bem complicado.(2 votos) - como a função theta pode assumir o formato de função haverá lugares em que a diferença entre os limites será maior ou menor conforme o perfil da função. em termos práticos o que isso significa computacionalmente falando..?(1 voto)