¿O (logn) es siempre un árbol?

Question

Siempre vemos que las operaciones en un árbol (de búsqueda binaria) tienen o (logn) el peor de los casos, el tiempo de ejecución debido a que la altura del árbol es logn. Me pregunto si se nos dice que un algoritmo tiene tiempo de ejecución en función de logn, por ejemplo, M + nlogn, ¿podemos concluir que debe involucrar un árbol (aumentado)?

EDITAR: Gracias a sus comentarios, ahora me doy cuenta de que Divide-Conquer y Binary Tree son muy similares visuales/conceptualmente. Nunca había hecho una conexión entre los dos. Pero pienso en un caso en el que O (logn) no es un algo conquistador de divide que involucra un árbol que no tiene propiedad de un árbol BST/AVL/rojo-negro.

Esa es la estructura de datos del conjunto disjunto con operaciones Find/Union, cuyo tiempo de ejecución es O (N + MLogn), siendo n el # de elementos y M el número de operaciones de búsqueda.

Avíseme si me falta STH, pero no puedo ver cómo Divide-Conquer entra en juego aquí. Solo veo en este caso (conjunto disjunto) que tiene un árbol sin propiedad BST y un tiempo de ejecución es una función de logn. Entonces, mi pregunta es sobre por qué/por qué no puedo hacer una generalización de este caso.

Answer 1

Lo que tienes es exactamente al revés. O(lg N) Generalmente significa algún tipo de algoritmo de división y conquistar, y una forma común de implementar dividir y conquistar es un árbol binario. Mientras que los árboles binarios son un subconjunto sustancial de todos los algoritmos de división y conquista, de todos modos son un subconjunto.

En algunos casos, puede transformar otros algoritmos de división y conquistar de manera bastante directa en árboles binarios (por ejemplo, los comentarios de otra respuesta ya han intentado reclamar una búsqueda binaria es similar). Sin embargo, solo para otro ejemplo obvio, un árbol multiway (por ejemplo, un árbol B, árbol B+ o árbol B*), mientras que claramente un árbol es tan claramente claramente no un árbol binario.

Una vez más, si desea lo suficientemente mal, puede estirar el punto de que un árbol de múltiples vías se puede representar como una especie de versión deformada de un árbol binario. Si lo desea, probablemente pueda estirar todas las excepciones hasta el punto de decir que todos son (al menos algo como) árboles binarios. Al menos para mí, sin embargo, todo lo que hace es hacer que el "árbol binario" sea sinónimo de "dividir y conquistar". En otras palabras, todo lo que logras es deformar el vocabulario y esencialmente borrar un término que es distinto y útil.

Answer 2

No, también puede buscar una matriz ordenada (por ejemplo). Pero no tomes mi palabra por eso http://en.wikipedia.org/wiki/binary_search_algorithm

Answer 3

Como ejemplo de contador:

given array 'a' with length 'n'
y = 0
for x = 0 to log(length(a))
    y = y + 1
return y

El tiempo de ejecución es O (log (n)), ¡pero no hay árbol aquí!

Answer 4

La respuesta es no. La búsqueda binaria de una matriz ordenada es O(log(n)).

Answer 5

Los algoritmos que toman tiempo logarítmico son comúnmente encontrado en operaciones en árboles binarios.

Ejemplos de o (logn):

• Encontrar un elemento en una matriz ordenada con una búsqueda binaria o un árbol de búsqueda equilibrado.

• Busque un valor en una matriz de entrada ordenada por bisección.

Answer 6

Como o (log (n)) es solo un límite superior también todos los algoritmos O (1) como function (a, b) return a+b; satisfacer la condición.

Pero tengo que estar de acuerdo en todos los algoritmos theta (log (n)) que se ven como algoritmos de árbol o al menos se pueden abstraer a un árbol.

Answer 7

Respuesta corta:

El hecho de que un algoritmo tenga log (n) como parte de su análisis no significa que esté involucrado un árbol. Por ejemplo, el siguiente es un algoritmo muy simple que es O(log(n)

for(int i = 1; i < n; i = i * 2)
  print "hello";

Como puede ver, no había ningún árbol involucrado. John, también proporciona un buen ejemplo sobre cómo se puede hacer la búsqueda binaria en una matriz ordenada. Ambos toman el tiempo O (log (n)), y hay otros ejemplos de código que podrían crearse o referenciarse. Así que no haga suposiciones basadas en la complejidad del tiempo asintótico, mire el código que sepa con certeza.

Más sobre árboles:

El hecho de que un algoritmo involucra "árboles" no implica O(logn) o. Debe conocer el tipo de árbol y cómo la operación afecta al árbol.

Algunos ejemplos:

• Ejemplo 1)

Insertar o buscar el siguiente árbol desequilibrado sería O(n).

• Ejemplo 2)

Insertar o buscar los siguientes árboles equilibrados tanto por O(log(n)).

Árbol binario equilibrado:

Árbol equilibrado de grado 3:

Comentarios adicionales

Si los árboles que está utilizando no tienen una forma de "equilibrar", hay una buena posibilidad de que sus operaciones sean O(n) tiempo no O(logn). Si usa árboles que se están equilibrando, los insertos normalmente toman más tiempo, ya que el equilibrio de los árboles normalmente ocurre durante la fase de inserción.