O (logn) toujours un arbre?

Question

Nous voyons toujours des opérations sur une (recherche binaire) arbre a O (logn) pire des cas, durée en raison de la hauteur des arbres est logn. Je me demande si on nous dit qu'un algorithme a en cours d'exécution du temps en fonction de log n, m + nlogn par exemple, peut-on conclure qu'il doit comporter un (augmentée) arbre?

EDIT: Merci à vos commentaires, je me rends compte maintenant diviser pour régner et arbre binaire sont tellement semblables visuellement / sur le plan conceptuel. Je ne l'avais jamais fait un lien entre les deux. Mais je pense que d'un cas où O (log n) est pas diviser pour régner algo qui implique un arbre qui n'a pas de propriété d'un BST / AVL / arbre rouge-noir.

C'est la structure de données de jeu disjoint avec les opérations de recherche / Union, dont la durée est O (N + MlogN), N étant le # d'éléments et M le nombre de Trouvez opérations.

S'il vous plaît laissez-moi savoir si je suis absent STH, mais je ne vois pas comment diviser pour régner entre en jeu ici. Je viens de voir dans ce (ensemble disjoint) cas où il a un arbre sans propriété BST et un temps d'exécution étant fonction de logN. Donc, ma question est de savoir pourquoi / pourquoi ne pas que je puisse faire une généralisation de ce cas.

Answer 1

Qu'est-ce que vous avez est exactement à l'envers. O(lg N) signifie généralement une sorte de diviser pour mieux régner algorithme, et d'une façon commune de mettre en œuvre diviser pour mieux régner est un arbre binaire. Bien que les arbres binaires sont un sous-ensemble important de tous les algorithmes de diviser pour régner, le sont un sous-ensemble de toute façon.

Dans certains cas, vous pouvez transformer d'autres algorithmes diviser pour mieux régner assez directement dans les arbres binaires (par exemple des commentaires sur une autre réponse ont déjà fait une tentative de prétendre une recherche binaire est similaire). Juste pour un autre exemple évident, cependant, un arbre multivoies (par exemple un B-tree, arbre B + ou B * arbre), alors clairement un arbre est tout aussi clairement pas un arbre binaire.

Encore une fois, si vous voulez assez mal, vous pouvez étirer le point qu'un arbre multivoies peut être représenté comme une sorte d'une version déformée d'un arbre binaire. Si vous le souhaitez, vous pouvez probablement étirer toutes les exceptions au point de dire que tous sont (au moins quelque chose comme) des arbres binaires. tout ce qui ne porte toutefois, au moins pour moi, est de faire « arbre binaire » synonyme de « diviser pour mieux régner ». En d'autres termes, tout ce que vous accomplissez est gauchissement le vocabulaire et oblitérer essentiellement un terme qui est à la fois distincte et utile.

Answer 2

Non, vous pouvez également rechercher binaire un tableau trié (par exemple). Mais ne prenez pas ma parole http://en.wikipedia.org/wiki/Binary_search_algorithm

Answer 3

Par contre exemple:

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

Le temps d'exécution est O (log (n)), mais pas d'arbre ici!

Answer 4

La réponse est non. recherche binaire d'un tableau est triée O(log(n)).

Answer 5

Les algorithmes prenant le temps logarithmique sont généralement trouvé dans les opérations sur les arbres binaires.

Des exemples de O (log n):

• Recherche d'un élément dans un tableau avec une recherche triée binaire ou un arbre de recherche équilibré.

• rechercher une valeur dans un tableau d'entrée triée par bissection.

Answer 6

O (log (n)) est seulement une limite supérieure aussi tous les algorithmes O (1) comme function (a, b) return a+b; satisfont à la condition.

Mais je suis d'accord tous les algorithmes Theta (log (n)) regarder un peu comme des algorithmes d'arbres ou au moins peut abstraire à un arbre.

Answer 7

Réponse courte:

Juste parce qu'un algorithme a log (n) dans le cadre de son analyse ne signifie pas qu'un arbre est impliqué. Par exemple, ce qui suit est un algorithme très simple qui est O(log(n)

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

Comme vous pouvez le voir, aucun arbre a été impliqué. John, fournit également un bon exemple de la façon dont la recherche binaire peut être fait sur un tableau trié. Ces deux prennent O (log (n)), et il y a d'autres exemples de code qui pourraient être créés ou référencés. Alors ne faites pas d'hypothèses fondées sur la complexité du temps asymptotique, regardez le code pour en être sûr.

Plus sur les arbres:

Juste parce qu'un algorithme implique des « arbres » ne signifie pas non plus O(logn). Vous devez connaître le type d'arbre et comment l'opération affecte l'arbre.

Quelques exemples:

• Exemple 1)

Insertion ou à la recherche de l'arbre asymétrique suivant serait O(n).

• Exemple 2)

Insertion ou rechercher les deux par O(log(n)) seraient arbres équilibrés suivants.

Binary Tree équilibré:

Arbre équilibré de degré 3:

Commentaires supplémentaires

Si les arbres que vous utilisez ne pas avoir un moyen de « l'équilibre » que il y a une bonne chance que vos opérations seront temps O(n) pas O(logn). Si vous utilisez des arbres qui sont auto équilibrage, puis insère normalement prendre plus de temps, comme l'équilibrage des arbres se produisent normalement au cours de la phase d'insertion.