Comment construire un tas peut-il être la complexité O (n) du temps?

Est-ce que quelqu’un peut aider à expliquer comment la création d’un tas peut être la complexité O (n)?

L’insertion d’un élément dans un tas est O(log n) et l’insertion est répétée n / 2 fois (les autres sont des feuilles et ne peuvent pas violer la propriété heap). Donc, cela signifie que la complexité devrait être O(n log n) , je pense.

En d’autres termes, pour chaque élément que nous “empilons”, il a le potentiel de filtrer une fois pour chaque niveau pour le tas jusqu’à présent (ce qui est des niveaux de log n).

Qu’est-ce que je rate?

Je pense qu’il y a plusieurs questions enterrées dans ce sujet:

  • Comment implémentez-vous buildHeap pour qu’il s’exécute dans le temps O (n) ?
  • Comment montrez-vous que buildHeap s’exécute en heure O (n) lorsqu’il est correctement implémenté?
  • Pourquoi cette même logique ne fonctionne-t-elle pas pour que le sorting du tas s’exécute dans le temps O (n) plutôt que dans O (n log n) ?

Souvent, les réponses à ces questions se concentrent sur la différence entre siftUp et siftDown . Faire le bon choix entre siftUp et siftDown est essentiel pour obtenir des performances O (n) pour buildHeap , mais ne fait rien pour aider à comprendre la différence entre buildHeap et heapSort en général. En effet, les implémentations correctes de buildHeap et de heapSort utiliseront uniquement siftDown . L’opération siftUp n’est nécessaire que pour effectuer des insertions dans un siftUp existant. Par exemple, elle sera utilisée pour implémenter une queue prioritaire à l’aide d’un siftUp binary.

J’ai écrit ceci pour décrire comment fonctionne un tas maximum. Il s’agit du type de segment de mémoire généralement utilisé pour le sorting du segment de mémoire ou pour une queue prioritaire où des valeurs plus élevées indiquent une priorité plus élevée. Un min heap est également utile; par exemple, lors de la récupération d’éléments avec des clés entières dans l’ordre croissant ou des chaînes dans l’ordre alphabétique. Les principes sont exactement les mêmes. changez simplement l’ordre de sorting.

La propriété heap spécifie que chaque nœud dans un segment binary doit être au moins aussi grand que ses deux enfants. En particulier, cela implique que le plus gros élément du tas est à la racine. Le tamisage et le tamisage sont essentiellement la même opération dans des directions opposées: déplacez un nœud incriminé jusqu’à ce qu’il satisfasse la propriété de tas:

  • siftDown échange un noeud trop petit avec son plus grand enfant (le déplaçant ainsi vers le bas) jusqu’à ce qu’il soit au moins aussi grand que les deux noeuds situés en dessous.
  • siftUp échange un noeud trop grand avec son parent (le déplaçant ainsi vers le haut) jusqu’à ce qu’il ne soit pas plus gros que le noeud situé au-dessus.

Le nombre d’opérations requirejs pour siftDown et siftUp est proportionnel à la distance que le nœud peut avoir à déplacer. Pour siftDown , il s’agit de la distance par rapport au bas de l’arborescence, de sorte que siftDown est coûteux pour les nœuds en haut de l’arborescence. Avec siftUp , le travail est proportionnel à la distance par rapport au sumt de l’arborescence, de sorte que siftUp est coûteux pour les nœuds au bas de l’arborescence. Bien que les deux opérations soient O (log n) dans le pire des cas, dans un tas, un seul nœud est en haut alors que la moitié des nœuds se trouve dans la couche inférieure. Donc, il ne devrait pas être surprenant que si nous devons appliquer une opération à chaque nœud, nous préférerions siftDown plutôt que siftUp .

La fonction buildHeap prend un tableau d’éléments non sortingés et les déplace jusqu’à ce qu’ils satisfassent tous à la propriété heap, produisant ainsi un buildHeap valide. Il y a deux approches possibles pour buildHeap utilisant les opérations siftUp et siftDown nous avons décrites.

  1. Commencez en haut du tas (au début du tableau) et appelez siftUp sur chaque élément. À chaque étape, les éléments précédemment sortingés (les éléments avant l’élément en cours dans le tableau) forment un segment de mémoire valide, et le sorting de l’élément suivant le place dans une position valide dans le tas. Après avoir sortingé chaque nœud, tous les éléments satisfont la propriété heap.

  2. Ou, allez dans la direction opposée: commencez à la fin du tableau et avancez vers l’avant. À chaque itération, vous passez au crible un élément jusqu’à ce qu’il se trouve au bon endroit.

Ces deux solutions produiront un tas valide. La question est: quelle implémentation de buildHeap est plus efficace? Sans surprise, c’est la deuxième opération qui utilise siftDown .

Soit h = log n la hauteur du tas. Le travail requirejs pour l’approche siftDown est donné par la sum

 (0 * n/2) + (1 * n/4) + (2 * n/8) + ... + (h * 1). 

Chaque terme de la sum a la distance maximale qu’un nœud à la hauteur donnée devra déplacer (zéro pour la couche inférieure, h pour la racine) multiplié par le nombre de nœuds à cette hauteur. En revanche, la sum pour appeler siftUp sur chaque nœud est

 (h * n/2) + ((h-1) * n/4) + ((h-2)*n/8) + ... + (0 * 1). 

Il devrait être clair que la deuxième sum est plus grande. Le premier terme seul est hn / 2 = 1/2 n log n , donc cette approche a au mieux la complexité O (n log n) . Mais comment prouver que la sum pour l’approche de siftDown est bien O (n) ? Une méthode (il y a d’autres parsings qui fonctionnent également) consiste à transformer la sum finie en une série infinie, puis à utiliser les séries de Taylor. Nous pouvons ignorer le premier terme, qui est zéro:

Série de Taylor pour la complexité de buildHeap

Si vous ne savez pas pourquoi chacune de ces étapes fonctionne, voici une justification pour le processus:

  • Les termes sont tous positifs, donc la sum finie doit être inférieure à la sum infinie.
  • La série est égale à une série de puissances évaluée à x = 1/2 .
  • Cette série de puissances est égale à (une fois constante) la dérivée de la série de Taylor pour f (x) = 1 / (1-x) .
  • x = 1/2 est dans l’intervalle de convergence de cette série de Taylor.
  • Par conséquent, nous pouvons remplacer la série de Taylor par 1 / (1-x) , différencier et évaluer pour trouver la valeur de la série infinie.

Puisque la sum infinie est exactement n , nous concluons que la sum finie n’est pas plus grande et est donc O (n) .

La question suivante est la suivante: s’il est possible d’exécuter buildHeap en temps linéaire, pourquoi le sorting du tas nécessite-t-il l’heure O (n log n) ? Eh bien, le sorting en tas comprend deux étapes. Tout d’abord, nous appelons buildHeap sur le tableau, ce qui nécessite du temps O (n) s’il est implémenté de manière optimale. L’étape suivante consiste à supprimer de manière répétée le plus gros élément du tas et à le placer à la fin du tableau. Comme nous supprimons un élément du tas, il y a toujours un point ouvert juste après la fin du tas où nous pouvons stocker l’article. Ainsi, le sorting de tas permet de classer l’ordre suivant en supprimant successivement le plus grand élément suivant et en le plaçant dans le tableau en commençant à la dernière position et en se déplaçant vers l’avant. C’est la complexité de cette dernière partie qui domine dans le sorting en tas. La boucle ressemble à ceci:

 for (i = n - 1; i > 0; i--) { arr[i] = deleteMax(); } 

Clairement, la boucle exécute O (n) fois ( n – 1 pour être précis, le dernier élément est déjà en place). La complexité de deleteMax pour un tas est O (log n) . Il est généralement implémenté en supprimant la racine (le plus gros élément restant dans le tas) et en la remplaçant par le dernier élément du tas, qui est une feuille, et par conséquent l’un des plus petits éléments. Cette nouvelle racine va certainement violer la propriété heap, vous devez donc appeler siftDown jusqu’à ce que vous la siftDown dans une position acceptable. Cela a également pour effet de déplacer l’élément suivant le plus grand jusqu’à la racine. Notez que, contrairement à buildHeap où, pour la plupart des nœuds, nous appelons siftDown depuis le bas de l’arbre, nous appelons maintenant siftDown depuis le haut de l’arborescence à chaque itération! Bien que l’arborescence diminue, elle ne rétrécit pas assez rapidement : la hauteur de l’arborescence rest constante jusqu’à ce que vous ayez supprimé la première moitié des nœuds (lorsque vous supprimez complètement la couche inférieure). Ensuite, pour le sortingmestre suivant, la hauteur est h – 1 . Donc, le travail total pour cette deuxième étape est

 h*n/2 + (h-1)*n/4 + ... + 0 * 1. 

Remarquez le commutateur: maintenant le cas de travail zéro correspond à un seul nœud et le cas de figure h correspond à la moitié des nœuds. Cette sum est O (n log n), tout comme la version inefficace de buildHeap implémentée avec siftUp. Mais dans ce cas, nous n’avons pas le choix puisque nous essayons de sortinger et nous avons besoin que le prochain article le plus important soit supprimé.

En résumé, le travail pour le sorting du tas est la sum des deux étapes: O (n) temps pour buildHeap et O (n log n) pour supprimer chaque nœud dans l’ordre , donc la complexité est O (n log n) . Vous pouvez prouver (en utilisant certaines idées de la théorie de l’information) que pour un sorting basé sur la comparaison, O (n log n) est le meilleur que vous pouvez espérer, donc il n’y a aucune raison d’être déçu. O (n) temps lié à ce que buildHeap fait.

Votre parsing est correcte. Cependant, ce n’est pas serré.

Il n’est pas vraiment facile d’expliquer pourquoi la construction d’un tas est une opération linéaire, vous devriez le lire.

Une excellente parsing de l’algorithme peut être vue ici .


L’idée principale est que dans l’algorithme build_heap , le coût réel de heapify n’est pas O(log n) pour tous les éléments.

Lorsque heapify est appelé, le temps d’exécution dépend de la distance dans laquelle un élément peut se déplacer dans l’arborescence avant la fin du processus. En d’autres termes, cela dépend de la hauteur de l’élément dans le tas. Dans le pire des cas, l’élément peut descendre jusqu’au niveau des feuilles.

Comptez le travail effectué niveau par niveau.

Au niveau le plus bas, il y a 2^(h) nœuds, mais nous heapify sur aucun de ceux-ci, donc le travail est 0. Au niveau suivant, il y a 2^(h − 1) nœuds, et chacun peut descendre d’un niveau. Au 3ème niveau depuis le bas, il y a 2^(h − 2) nœuds, et chacun peut descendre de 2 niveaux.

Comme vous pouvez le voir, toutes les opérations heapify ne sont pas O(log n) , c’est pourquoi vous obtenez O(n) .

Intuitivement:

“La complexité devrait être O (nLog n) … pour chaque élément que nous” empilons “, il a le potentiel de devoir filtrer une fois pour chaque niveau du tas (ce qui est le niveau de log n).”

Pas assez. Votre logique ne produit pas de lien étroit – elle surestime la complexité de chaque tas. Si construit de bas en haut, l’insertion (heapify) peut être très inférieure à O(log(n)) . Le processus est le suivant:

(Étape 1) Les n/2 premiers éléments vont sur la rangée inférieure du tas. h=0 , donc heapify n’est pas nécessaire.

(Étape 2) Les 2/2 éléments suivants vont sur la rangée 1 en partant du bas. h=1 , les filtres heapify 1 level down.

(Étape i ) Les prochains n/2 i éléments vont dans la rangée i en partant du bas. h=i , les filtres heapify i bas.

(Step log (n) ) Le dernier élément n/2 log 2 (n) = 1 va dans le log(n) lignes log(n) à partir du bas. h=log(n) , heapify filtre le log(n) niveaux bas.

AVIS: après la première étape, la 1/2 des éléments (n/2) sont déjà dans le tas et nous n’avons même pas besoin d’appeler une fois heapify. En outre, notez que seul un élément unique, la racine, supporte la complexité complète du log(n) .


Théoriquement:

Les étapes totales N pour construire un tas de taille n peuvent être écrites mathématiquement.

A la hauteur i , nous avons montré (ci-dessus) qu’il y aura n/2 i+1 éléments à appeler heapify, et nous soaps que heapify à la hauteur i est O(i) . Cela donne:

entrer la description de l'image ici

La solution à la dernière sommation peut être trouvée en prenant la dérivée des deux côtés de l’équation de la série géomésortingque bien connue:

entrer la description de l'image ici

Finalement, le twigment de x = 1/2 dans l’équation ci-dessus donne 2 . Le twigr dans la première équation donne:

entrer la description de l'image ici

Ainsi, le nombre total d’étapes est de taille O(n)

Ce serait O (n log n) si vous construisiez le tas en insérant des éléments de manière répétée. Cependant, vous pouvez créer un nouveau tas plus efficacement en insérant les éléments dans un ordre arbitraire, puis en appliquant un algorithme pour les “emstackr” dans le bon ordre (en fonction du type de tas, bien sûr).

Voir http://en.wikipedia.org/wiki/Binary_heap , “Construire un tas” pour un exemple. Dans ce cas, vous travaillez essentiellement à partir du niveau inférieur de l’arborescence, en échangeant les nœuds parents et enfants jusqu’à ce que les conditions du tas soient satisfaites.

En construisant un tas, disons que vous prenez une approche ascendante.

  1. Vous prenez chaque élément et le comparez avec ses enfants pour vérifier si la paire est conforme aux règles du segment de mémoire. Les feuilles sont donc incluses dans le tas gratuitement. C’est parce qu’ils n’ont pas d’enfants.
  2. En montant vers le haut, le pire scénario pour le nœud juste au-dessus des feuilles serait une comparaison (au maximum, ils seraient comparés à une seule génération d’enfants).
  3. Plus loin, leurs parents immédiats peuvent être comparés à deux générations d’enfants.
  4. Dans la même direction, vous obtiendrez des comparaisons log (n) pour la racine dans le pire des cas. et log (n) -1 pour ses enfants immédiats, log (n) -2 pour leurs enfants immédiats et ainsi de suite.
  5. Donc, en résumé, vous arrivez à quelque chose comme log (n) + {log (n) -1} * 2 + {log (n) -2} * 4 + ….. + 1 * 2 ^ {( logn) -1} qui n’est rien d’autre que O (n).

Comme on le sait, la hauteur d’un tas est log (n) , où n représente le nombre total d’éléments.
Lorsque nous effectuons une opération heapify, les éléments du dernier niveau ( h ) ne bougeront même pas d’un seul pas.
Le nombre d’éléments au second niveau ( h-1 ) est de 2 h-1 et ils peuvent se déplacer à 1 niveau maximum (pendant l’entraînement).
De même, pour le ieme niveau, nous avons 2 éléments qui peuvent déplacer les positions.

Donc nombre total de coups = S = 2 h * 0 + 2 h-1 * 1 + 2 h-2 * 2 + … 2 0 * h

S = 2 h {1/2 + 2/2 2 + 3/2 3 + … h / 2 h } ———————– ————————–1
c’est la série AGP , pour résoudre cette division des deux côtés par 2
S / 2 = 2 h {1/2 2 + 2/2 3 + … h / 2 h + 1 } ———————– ————————– 2
en soustrayant l’équation 2 de 1 donne
S / 2 = 2 h { 1/2 + 1/2 2 + 1/2 3 + … + 1/2 h + h / 2 h + 1 }
S = 2 h + 1 { 1/2 + 1/2 2 + 1/2 3 + … + 1/2 h + h / 2 h + 1 }
maintenant 1/2 + 1/2 2 + 1/2 3 + … + 1/2 h diminue GP dont la sum est inférieure à 1 (quand h tend vers l’infini, la sum tend vers 1). En analysant plus en détail, prenons une limite supérieure à la sum qui est 1.
Cela donne S = 2 h + 1 {1 + h / 2 h + 1 }
= 2 h + 1 + h
~ 2h + h
comme h = log (n) , 2 h = n

Donc S = n + log (n)
T (C) = O (n)

En cas de construction du tas, on part de la hauteur, logn -1 (où logn est la hauteur de l’arbre des n éléments). Pour chaque élément présent à la hauteur ‘h’, nous allons à max jusqu’à (logn -h) height down.

  So total number of traversal would be:- T(n) = sigma((2^(logn-h))*h) where h varies from 1 to logn T(n) = n((1/2)+(2/4)+(3/8)+.....+(logn/(2^logn))) T(n) = n*(sigma(x/(2^x))) where x varies from 1 to logn and according to the [sources][1] function in the bracket approaches to 2 at infinity. Hence T(n) ~ O(n) 

Les insertions successives peuvent être décrites par:

 T = O(log(1) + log(2) + .. + log(n)) = O(log(n!)) 

En approchant de près, n! =~ O(n^(n + O(1))) n! =~ O(n^(n + O(1))) , donc T =~ O(nlog(n))

J’espère que cela vous aidera, la façon optimale pour O(n) utiliser l’algorithme de compilation pour un ensemble donné (l’ordre n’a pas d’importance).

@bcorso a déjà démontré la preuve de l’parsing de complexité. Mais pour ceux qui continuent d’apprendre la complexité de l’parsing, j’ai ceci à append:

La base de votre erreur d’origine est due à une mauvaise interprétation de la signification de l’instruction, “l’insertion dans un tas prend du temps O (log n)”. L’insertion dans un tas est en effet O (log n), mais vous devez reconnaître que n est la taille du tas pendant l’insertion .

Dans le contexte de l’insertion de n objects dans un tas, la complexité de la deuxième insertion est O (log n_i) où n_i est la taille du tas à l’insertion i. Seule la dernière insertion a une complexité de O (log n).

J’aime beaucoup l’explication de Jeremy West … une autre approche très facile à comprendre est donnée ici http://courses.washington.edu/css343/zander/NotesProbs/heapcomplexity

Depuis, buildheap dépend de l’utilisation dépend de l’approche heapify et shiftdown qui dépend de la sum des hauteurs de tous les nœuds. Donc, pour trouver la sum de la hauteur des nœuds qui est donnée par S = sommation de i = 0 à i = h de (2 ^ i * (hi)), où h = logn est la hauteur de l’arbre résolvant s, on obtient s = 2 ^ (h + 1) – 1 – (h + 1) puisque, n = 2 ^ (h + 1) – 1 s = n – h – 1 = n- logn – 1 s = O (n), et la complexité de buildheap est donc O (n).

“Le temps linéaire lié à la construction Heap peut être montré en calculant la sum des hauteurs de tous les nœuds du tas, qui est le nombre maximum de lignes pointillées. Pour l’arbre binary parfait de hauteur h contenant N = 2 ^ h + 1) – 1 nœuds, la sum des hauteurs des nœuds est N – H – 1. C’est donc O (N). ”

Fondamentalement, le travail est effectué uniquement sur les nœuds non-feuille lors de la construction d’un tas … et le travail effectué est la quantité de permutation pour satisfaire les conditions de tas … en d’autres termes (dans le pire des cas) la quantité est proportionnelle à la hauteur du nœud … dans l’ensemble, la complexité du problème est proportionnelle à la sum des hauteurs de tous les nœuds non-feuilles..qui est (2 ^ h + 1 – 1) -h-1 = nh-1 = Sur)

Preuve de O (n)

La preuve n’est pas sophistiquée et assez simple, j’ai seulement prouvé le cas pour un arbre binary complet, le résultat peut être généralisé pour un arbre binary complet.

pense que tu fais une erreur. Jetez un coup d’oeil à ceci: http://golang.org/pkg/container/heap/ Construire un tas isn’y O (n). Cependant, l’insertion est O (lg (n). Je suppose que l’initialisation est O (n) si vous définissez une taille de segment b / c, le segment doit allouer de l’espace et configurer la structure de données. Si vous avez n éléments à placer dans le tas alors oui, chaque insertion est lg (n) et il y a n éléments, donc vous obtenez n * lg (n) comme indiqué