Estou aprendendo sobre os tempos de execução da Big O Notation e os tempos amortizados. Eu entendo a noção de O(n) tempo linear, significando que o tamanho do input afeta o crescimento do algoritmo proporcionalmente...e o mesmo vale, por exemplo, para o tempo quadrático O(n2) etc..mesmo algoritmos, como geradores de permutação, com O(n!) tempos, que crescem por fatores.
Por exemplo, a seguinte função é O(n) porque o algoritmo cresce em proporção à sua entrada n:
f(int n) {
int i;
for (i = 0; i < n; ++i)
printf("%d", i);
}
Da mesma forma, se houvesse um loop aninhado, o tempo seria O(n2).
Mas o que é exactamente O(log n)? Por exemplo, o que significa dizer que a altura de uma árvore binária completa é O(log n)?
Eu sei (talvez não em grandes detalhes) o que é Logaritmo, no sentido de que: log10 100 = 2, mas não consigo entender como identificar uma função com um tempo logarítmico.
Tempo de execução logarítmico (O(log n)
) significa essencialmente que o tempo de execução cresce em proporção ao logaritmo do tamanho da entrada - como exemplo, se 10 itens levam no máximo algum tempo x
, e 100 itens levam no máximo, digamos, 2x
, e 10.000 itens levam no máximo 4x
, então parece um O(log n)
complexidade de tempo.
Isto significa simplesmente que o tempo necessário para esta tarefa cresce com log(n) (exemplo : 2s para n = 10, 4s para n = 100, ...). Leia os artigos da Wikipedia em Algoritmo de Busca Binária e Grande Notação O para mais precisões.
O exemplo binário completo é O(ln n) porque a pesquisa se parece com isto:
1 2 3 4 5 6 7 8 9 10 11 12
Procurando por 4 rendimentos 3 acessos: 6, 3 e depois 4. E log2 12 = 3, o que é uma boa aproximação de quantos acertos onde é necessário.