La complexité du temps d'insertion de l'implémentation de la liste triée de la file d'attente prioritaire O (n) est-elle établie?

Question

De wikipedia:

Liste triée mise en œuvre: Comme une ligne de commande au supermarché, mais où les gens importants arrivent à « couper » en devant des gens moins importants. (O (n) temps d'insertion, O (1) get-la prochaine fois, O (n * log (n)) pour construire)

Je pense que si la recherche de la position d'insertion avec l'algorithme de recherche binaire , la complexité du temps d'insertion doit être O (log (n)). Ici, je traite l'ordre d'arrivée des travaux comme un facteur de priorité.

Alors, est-ce que je me trompe ou wikipedia est incorrect?

Update: Selon la définition stricte de la liste de TAOCP:

Une liste linéaire est une séquence de n> = 0 1 noeuds X, X [2], ..., X [n] dont les propriétés structurelles essentielles n'impliquent que les positions relatives entre les éléments tels qu'ils apparaissent dans une ligne .

Je suppose que la liste wikipedia se référer n'est pas liée liste, et il pourrait être tableau.

merci.

Answer 1

si la liste chaînée de la, il vous ne pouvez pas sauvegardé faire une recherche binaire ainsi; trouver le point d'insertion est O (n), insertion réellement est O (1) que vous venez de changer les nœuds adjacents, global O (n).

si son tableau vous pouvez faire sauvegardé une recherche binaire ainsi; trouver le point d'insertion est O (log (n)), mais l'insertion dans un tableau est O (n) que vous pouvez avoir à déplacer tous les éléments de la matrice, O globale (n)

cela est Pourquoi avez-vous réellement arborescence/heap sauvegardé pour que toutes les opérations puissent être O (log (n))

Answer 2

Il semble que dans votre citation, Wikipedia se réfère à une file d'attente prioritaire soutenue par une liste triée, plutôt que par un tas. Pour insérer un élément dans une liste triée, il faut un temps O (n) (en supposant que nous maintenons son ordre de tri).

Answer 3

La recherche binaire est en effet O(log n) mais la recherche binaire fonctionne sur les tableaux - cela fonctionne parce que vous pouvez accéder à n'importe quel élément dans O (1).

Cependant, dans la littérature lorsque vous voyez la liste des termes, vous devriez penser à des listes liées. Dans une liste par conséquent, vous n'avez pas le temps d'accès O (1), mais vous devez plutôt rechercher la position "à la main" - l'insertion d'un élément prend donc O (n).

Answer 4

Le temps d'insertion le plus défavorable dans une liste triée est O (n). Le pire des cas consiste à insérer l'élément le plus élevé dans la liste. Pour ce faire, vous devez parcourir tous les éléments, puis insérer à la fin. La raison pour laquelle vous n'obtenez pas de recherche binaire est que seul l'élément auquel vous pouvez accéder dans la liste est le successeur de votre élément actuel, c'est-à-dire aucun accès aléatoire.

Answer 5

Wikipédia est correct. Comme d'autres l'ont déjà dit, les listes ne sont pas accessibles au hasard, donc vous devez visiter chaque nœud entre A et B avant d'arriver à B. Cela rend la recherche binaire inutile car traverser la liste est O (n), donc vous finissez par faire plus travail que si vous venez d'itérer sur la liste une fois. Vous pouvez mettre en cache les nœuds de début, de milieu et de fin dans un tampon séparé et vérifier ceux-ci en premier. Cependant, cela aurait juste le même effet que l'utilisation de plusieurs listes. La structure de données skip-list pousse cette idée un peu plus loin.

Utilisez donc un tas d'accès aléatoire à la place, ou peut-être une liste de sauts: http://en.wikipedia.org/wiki/Skip_list selon vos besoins.