Notação Big-θ (Grande-Theta)

Vamos ver uma implementação simples da busca linear:

Vamos indicar o tamanho do array (array.length) como $n$n. O número máximo de vezes que um laço "for" pode ser executado é $n$n, e esse pior caso ocorre quando o valor procurado não está presente no array.

A cada iteração do laço, há diversas coisas a serem feitas:

Cada uma dessas pequenas computações são executadas em um tempo constante a cada iteração. Se o laço "for" se repete $n$n vezes, então o tempo para todos as $n$n iterações é $c_1 \cdot n$c, start subscript, 1, end subscript, dot, n, em que $c_1$c, start subscript, 1, end subscript é a soma de vezes para as computações em uma iteração. Agora, não podemos afirmar qual é o valor de $c_1$c, start subscript, 1, end subscript, 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 guess como 0) e possivelmente retornar -1 no final. Vamos chamar o tempo dessa sobrecarga de $c_2$c, start subscript, 2, end subscript, que também é uma constante. Portanto, o tempo total para a busca linear no pior caso é $c_1 \cdot n + c_2$c, start subscript, 1, end subscript, dot, n, plus, c, start subscript, 2, end subscript.

Como dissemos, o fator constante $c_1$c, start subscript, 1, end subscript e o termo de baixa ordem $c_2$c, start subscript, 2, end subscript 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 é $\Theta(n)$\Theta, left parenthesis, n, right parenthesis. 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 é $\Theta(n)$\Theta, left parenthesis, n, right parenthesis, estamos dizendo que, quando $n$n fica grande o bastante, o tempo de execução é de pelo menos $k_1 \cdot n$k, start subscript, 1, end subscript, dot, n e, no máximo, de $k_2 \cdot n$k, start subscript, 2, end subscript, dot, n para quaisquer constantes $k_1$k, start subscript, 1, end subscript e $k_2$k, start subscript, 2, end subscript. É assim que devemos pensar no $\Theta(n)$\Theta, left parenthesis, n, right parenthesis:

Para valores pequenos de $n$n, não importa como o tempo de execução se compara com $k_1 \cdot n$k, start subscript, 1, end subscript, dot, n ou $k_2 \cdot n$k, start subscript, 2, end subscript, dot, n. Mas quando $n$n fica grande o bastante — sobre ou à direita da linha pontilhada — o tempo de execução deve ficar entre $k_1 \cdot n$k, start subscript, 1, end subscript, dot, n e $k_2 \cdot n$k, start subscript, 2, end subscript, dot, n. Enquanto essas constantes $k_1$k, start subscript, 1, end subscript e $k_2$k, start subscript, 2, end subscript existirem, dizemos que o tempo de execução é $\Theta(n)$\Theta, left parenthesis, n, right parenthesis.

Não estamos restritos a apenas $n$n na notação Θ. Podemos usar qualquer função, como $n^2$n, squared, $n \log_2 n$n, log, start base, 2, end base, n, ou qualquer outra função de $n$n. Aqui está um exemplo de como pensar em um tempo de execução que é $\Theta(f(n))$\Theta, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis para alguma função $f(n)$f, left parenthesis, n, right parenthesis:

Uma vez que o $n$n fica grande o suficiente, o tempo de execução fica entre $k_1 \cdot f(n)$k, start subscript, 1, end subscript, dot, f, left parenthesis, n, right parenthesis e $k_2 \cdot f(n)$k, start subscript, 2, end subscript, dot, f, left parenthesis, n, right parenthesis.

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 $6n^2 + 100n + 300$6, n, squared, plus, 100, n, plus, 300 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 $100n + 300$100, n, plus, 300, e você simplesmente diz que o tempo de execução é $\Theta(n^2)$\Theta, left parenthesis, n, squared, right parenthesis.

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.