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 ( . O número máximo de vezes que um laço "for" pode ser executado é , e esse pior caso ocorre quando o valor procurado não está presente no array.
array.length
) como A cada iteração do laço, há diversas coisas a serem feitas:
- comparar a variável
guess
comarray.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 vezes, então o tempo para todos as iterações é , em que é a soma de vezes para as computações em uma iteração. Agora, não podemos afirmar qual é o valor de , porque ele depende da velocidade do computador, da linguagem de programação usada, do compilador ou interpretador que traduz o código fonte em código executável e de outros fatores.
Esse código possui uma pequena sobrecarga extra, para configurar o laço "for" (o que inclui inicializar o valor de , que também é uma constante. Portanto, o tempo total para a busca linear no pior caso é .
guess
como 0) e possivelmente retornar -1
no final. Vamos chamar o tempo dessa sobrecarga de Como dissemos, o fator constante e o termo de baixa ordem não nos dizem nada sobre a taxa de crescimento do tempo de execução. O importante é que o pior tempo de execução possível da busca linear aumenta de acordo com o tamanho do array . A notação que usamos para esse tempo de execução é . Esta é a letra grega "theta" maiúscula e dizemos "Theta-grande de " ou apenas "Theta de ."
Quando dizemos que um tempo de execução em particular é , estamos dizendo que, quando fica grande o bastante, o tempo de execução é de pelo menos e, no máximo, de para quaisquer constantes e . É assim que devemos pensar no :
Para valores pequenos de , não importa como o tempo de execução se compara com ou . Mas quando fica grande o bastante — sobre ou à direita da linha pontilhada — o tempo de execução deve ficar entre e . Enquanto essas constantes e existirem, dizemos que o tempo de execução é .
Não estamos restritos a apenas na notação Θ. Podemos usar qualquer função, como , , ou qualquer outra função de . Aqui está um exemplo de como pensar em um tempo de execução que é para alguma função :
Uma vez que o fica grande o suficiente, o tempo de execução fica entre e .
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 microssegundos. Ou talvez sejam milissegundos. Quando você usa a notação Θ, você não especifica isso. Você também descarta o fator 6 e os termos de ordem inferior , e você simplesmente diz que o tempo de execução é .
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 . "Limite restrito" porque definimos o tempo de execução para um fator constante superior e inferior.
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)