¿Es O (logn) siempre un árbol?

Question

Siempre vemos que las operaciones en un árbol (búsqueda binaria) tienen el peor tiempo de ejecución de O (logn) debido a que la altura del árbol es logn. Me pregunto si nos dicen 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)?

EDIT: Gracias a sus comentarios, ahora me doy cuenta de que divide-conquista y el árbol binario son muy similares visualmente/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 de divide y vencerás que involucra un árbol que no tiene ninguna propiedad de un árbol BST/AVL/rojo-negro.

Esa es la estructura de datos set disjunta con operaciones Find/Union, cuyo tiempo de ejecución es O (N + MlogN), siendo N el n. ° de elementos y M el número de operaciones de búsqueda.

Por favor, avíseme si me falta algo, pero no puedo ver cómo divide-conquista entra en juego aquí. Acabo de ver en este caso (conjunto disjunto) que tiene un árbol sin propiedad BST y que el tiempo de ejecución es una función de logN. Entonces mi pregunta es por qué/por qué no puedo hacer una generalización a partir de este caso.

Answer 1

Lo que tienes es exactamente al revés. O(lg N) generalmente significa algún tipo de algoritmo de divide y vencerás, y una forma común de implementar divide y vencerás es un árbol binario. Si bien 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 conquista de manera bastante directa en árboles binarios (por ejemplo, los comentarios sobre otra respuesta ya han intentado afirmar que una búsqueda binaria es similar). Solo para otro ejemplo obvio, sin embargo, un árbol de múltiples vías (por ejemplo, un árbol B, árbol B + o árbol B *), mientras que claramente un árbol es tan claro no un árbol binario.

Una vez más, si quieres bastante mal, puedes estirar el punto de que un árbol de varias 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 todas ellas son (al menos algo así como) árboles binarios. Al menos para mí, sin embargo, todo lo que hace es hacer que "árbol binario" sea sinónimo de "dividir y conquistar". En otras palabras, todo lo que logra es deformar el vocabulario y, en esencia, borrar un término que es distinto y útil.

Answer 2

No, también puede buscar binaria una matriz ordenada (por ejemplo). Pero no tome mi palabra para ella http://en.wikipedia.org/wiki/Binary_search_algorithm

Answer 3

Como contraejemplo:

tiempo

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

La ejecución es O (log (n)), pero ningún árbol aquí!

Answer 4

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

Ejemplos de O (log n):

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

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

Answer 5

La respuesta es no. La búsqueda binaria de una matriz ordenada es O(log(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; satisfacen la condición.

Pero tengo que aceptar que todos los algoritmos Theta (log (n)) parecen un poco algoritmos de árbol o al menos se pueden abstraer a un árbol.

Answer 7

respuesta corta:

hecho de que un algoritmo tiene log (n) como parte de su análisis no significa que un árbol se tratara. 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 se puede ver, hay árbol estaba involucrado. John, también proporciona un buen ejemplo de cómo se puede realizar 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 hagas suposiciones basadas en la complejidad del tiempo asintótico, mira el código para estar seguro.

Más sobre los árboles:

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

algunos ejemplos:

• Ejemplo 1)

insertar o buscando el siguiente árbol desequilibrado serían O(n).

• Ejemplo 2)

Inserción o buscar en los siguientes árboles equilibrados haría tanto por O(log(n)).

equilibrado Binary Tree:

árbol equilibrado de Grado 3:

Comentarios adicionales

Si los árboles que está utilizando no tienen una forma de "equilibrar" que hay un buen posibilidad de que sus operaciones sean O(n) vez no O(logn). Si usa árboles que se auto equilibran, entonces las inserciones normalmente toman más tiempo, ya que el equilibrio de los árboles normalmente ocurre durante la fase de inserción.