Na notação Big-O para estruturas de árvore: Por que algumas fontes referem-se a O (logN) e outras a O (h)? - algoritmo, estruturas de dados, árvore, big-o, árvore de pesquisa binária

Ao pesquisar a complexidade de qualquer algoritmo que atravessa uma árvore de pesquisa binária, vejo duas maneiras diferentes de expressar a mesma coisa:

Versão 1: o algoritmo transversal, na pior das hipóteses, compara uma vez por altura da árvore; portanto, a complexidade é O(h).

Versão 2: o algoritmo transversal, na pior das hipóteses, compara uma vez por altura da árvore; portanto, a complexidade é O(logN).

Parece-me que a mesma lógica está em ação, mas autores diferentes usam logN ou h. Alguém pode me explicar por que esse é o caso?

Respostas:

Se sua árvore binária estiver equilibrada para que cada nó tenha exatamente dois nós filhos, o número de nós na árvore será exatamente N = 2^h - 1, então a altura é o logaritmo do número de elementos (e da mesma forma para qualquer nárvore).

Uma árvore arbitrária e sem restrições pode parecer totalmente diferente; por exemplo, ele poderia ter apenas um nó em cada nível, então N = h nesse caso. Portanto, a altura é a medida mais geral, no que se refere às comparações reais, mas sob a suposição adicional de equilíbrio, você pode expressar a altura como o logaritmo do número de elementos.

O valor correto para o pior momento parasearch is tree é O (h), onde h é a altura de uma árvore. Se você estiver usando uma árvore de pesquisa balanceada (onde a altura da árvore é O (log n)), o tempo de pesquisa é na pior das hipóteses O (log n). Dito isto, nem todas as árvores estão equilibradas. Por exemplo, aqui está uma árvore com altura n - 1:

1

2

3

...

n

Aqui, h = O (n), então a pesquisa é O (n). É correto dizer que o tempo de pesquisa também é O (h), mas h ≠ O (log n) nesse caso e seria errado afirmar que o tempo de pesquisa era O (log n).

Em resumo, O (h) é o limite correto. O (log n) é o limite correto em uma árvore de pesquisa equilibrada quando a altura é no máximo O (log n), mas nem todas as árvores têm tempo de pesquisa O (log n) porque podem estar desequilibradas.

Espero que isto ajude!

O (h) se refere a uma árvore binária que é classificada, mas não balanceada

O (logn) se refere a uma árvore que é classificada e equilibrada

É uma espécie de duas maneiras de dizer a mesma coisa, porque sua árvore binária equilibrada média de altura "h" terá cerca de 2 ^ h nós.

Dependendo do contexto, height ou #nodes podem ser mais relevantes, e é isso que você verá referenciado.

porque o (h) oito de uma árvore equilibrada varia conforme o logaritmo do (N) número de elementos