algorithm - programacion - En notación Big-O para estructuras de árbol: ¿Por qué algunas fuentes se refieren a O(logN) y algunas a O(h)?

notacion de un algoritmo

Question

Al investigar la complejidad de cualquier algoritmo que atraviesa un árbol de búsqueda binaria, veo dos maneras diferentes de expresar lo mismo:

Versión n. ° 1: el algoritmo transversal en el peor de los casos se compara una vez por altura del árbol; por lo tanto, la complejidad es O(h) .

Versión n. ° 2: el algoritmo transversal en el peor de los casos se compara una vez por altura del árbol; por lo tanto, la complejidad es O(logN) .

Me parece que funciona la misma lógica, pero diferentes autores usan logN o h . ¿Puede alguien explicarme por qué es este el caso?

Answer 1

El valor correcto para el peor de los casos de búsqueda es tree es O (h), donde h es la altura de un árbol. Si está utilizando un árbol de búsqueda balanceado (uno donde la altura del árbol es O (log n)), entonces el tiempo de búsqueda es el caso peor O (log n). Dicho esto, no todos los árboles están equilibrados. Por ejemplo, aquí hay un árbol con altura n - 1:

1
 /
  2
   /
    3
     /
     ...
       /
        n

Aquí, h = O (n), entonces la búsqueda es O (n). Es correcto decir que el tiempo de búsqueda también es O (h), pero h ≠ O (log n) en este caso y sería erróneo afirmar que el tiempo de búsqueda fue O (log n).

En resumen, O (h) es el límite correcto. O (log n) es el límite correcto en un árbol de búsqueda balanceado cuando la altura es como máximo O (log n), pero no todos los árboles tienen tiempo de búsqueda O (log n) porque pueden estar desequilibrados.

¡Espero que esto ayude!

Answer 2

Es una especie de dos formas de decir lo mismo, porque el árbol binario equilibrado promedio de altura ''h'' tendrá alrededor de 2 ^ h de nodos.

Dependiendo del contexto, la altura o los nodos pueden ser más relevantes, y eso es lo que verás referenciado.

Answer 3

O (h) se referiría a un árbol binario que está ordenado pero no equilibrado

O (logn) se referiría a un árbol que está ordenado y equilibrado

Answer 4

Si su árbol binario está equilibrado para que cada nodo tenga exactamente dos nodos secundarios, entonces la cantidad de nodos en el árbol será exactamente N = 2 ^h - 1, por lo que la altura es el logaritmo de la cantidad de elementos (y de manera similar para cualquier nodo). completar nary arbol).

Sin embargo, un árbol arbitrario y no restringido puede parecer totalmente diferente; por ejemplo, podría tener un nodo en cada nivel, entonces N = h en ese caso. Entonces, la altura es la medida más general, ya que se relaciona con las comparaciones reales, pero bajo el supuesto adicional de equilibrio puede expresar la altura como el logaritmo de la cantidad de elementos.

Answer 5

porque el (h) ocho de un árbol equilibrado varía según el registro de la (N) cantidad de elementos