Vamos ver uma implementação simples da busca linear:
var doLinearSearch = function(array) {
for (var guess = 0; guess < array.length; guess++) {
if (array[guess] === targetValue) {
return guess;  // encontrei!
    }
}
return -1;  // nao encontrei
};
Denotaremos o tamanho do array (array.length) por n n . O número máximo de vezes que o laço for pode executar é n n , e este pior caso ocorre quando o valor que está sendo procurado não está presente no array. Cada vez que o laço for itera, ele faz várias coisas: compara sugestões com o array.length; compara array[sugestão] com o valorBuscado; possivelmente retorna o valor da sugestão; e incrementa a sugestão. Cada uma dessas pequenas computações leva um período de tempo constante sempre que é executada. Se o laço for se repete n n vezes, então o tempo gasto por todas as n n iterações é c1n c_1 \cdot n , onde c1 c_1 é a soma dos tempos das computações de uma iteração do laço for. Agora, podemos dizer que o valor de c1 c_1 é, dependente da velocidade do computador, da linguagem de programação usada, do compilador ou interpretador que traduziu o programa em código executável, e outros fatores. Este código tem um pequeno bit de overhead extra, para a criação do laço for (incluindo a inicialização da sugestão para 0) e possivelmente retornando -1 no final. Vamos chamar este overhead de c2 c_2 , que também é uma constante. Therefore, the total time for linear search in the worst case is c1n+c2 c_1 \cdot n + c_2 .
Como dissemos, o fator constante c1 c_1 e o termo de baixa ordem c2 c_2 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 n n . A notação que usamos para esse tempo de execução é Θ(n) \Theta(n) . Esta é a letra grega "theta" maiúscula e dizemos "Theta-grande de n n " ou apenas "Theta de n n ."
Quando dizemos que um tempo de execução em particular é Θ(n) \Theta(n) , estamos dizendo que, quando n n fica grande o bastante, o tempo de execução é de pelo menos k1n k_1 \cdot n e, no máximo, de k2n k_2 \cdot n para quaisquer constantes k1 k_1 e k2 k_2 . É assim que devemos pensar no Θ(n) \Theta(n) :
Para valores pequenos de n n , não nos importamos com como o tempo de execução se compara com k1n k_1 \cdot n ou k2n k_2 \cdot n . Mas quando n n fica grande o bastante — sobre ou do lado direito da linha pontilhada — o tempo de execução deve ficar entre k1n k_1 \cdot n e k2n k_2 \cdot n . As long as these constants k1 k_1 and k2 k_2 exist, we say that the running time is Θ(n) \Theta(n) .
Não estamos restritos a apenas n n na notação big-Θ. Podemos usar qualquer função, como n2 n^2 , nlgn n \lg n , ou qualquer outra função de n n . Aqui está um exemplo de como pensar em um tempo de execução que é Θ(f(n)) \Theta(f(n)) para alguma função f(n) f(n) :
Uma vez que o n n fica grande o suficiente, o tempo de execução fica entre k1f(n) k_1 \cdot f(n) e k2f(n) k_2 \cdot f(n) .
Na prática, simplesmente descartamos fatores constantes e termos de ordem baixa. Outra vantagem de usar a notação bit-Θ é que não temos que nos preocupar sobre quais unidades de tempo estamos usando. Por exemplo, suponha que você tenha calculado que um tempo de execução é de 6n2+100n+300 6n^2 + 100n + 300 microssegundos. Ou talvez sejam milissegundos. Quando você usa a notação big-Θ, você não diz. You also drop the factor 6 and the low-order terms 100n+300 100n + 300 , and you just say that the running time is Θ(n2) \Theta(n^2) .
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 n n . "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.
Carregando