Comment la construction d'un tas peut-elle être une complexité temporelle O(n)?

Votre analyse est correcte. Cependant, il n'est pas serré.

Il n'est pas vraiment facile d'expliquer pourquoi construire un tas est une opération linéaire, vous devriez mieux le lire.

Un excellente analyse de l'algorithme peut être vu ici.

L'idée principale est que dans le build_heap algorithme de la réelle heapify coût 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 d'un élément pouvant descendre dans l'arborescence avant le processus se termine. En d'autres termes, il dépend de la hauteur de l'élément dans le tas. Dans le pire des cas, l'élément peut aller jusqu'au niveau de la feuille.

Comptons le travail effectué niveau par niveau.

Au niveau le plus bas, il y a des nœuds 2^(h), mais nous n'appelons pas heapify sur aucun d'entre eux, donc le travail est 0. Au niveau suivant, il y a des nœuds 2^(h − 1), et chacun peut descendre de 1 niveau. Au 3ème niveau à partir du bas, il y a des nœuds 2^(h − 2), et chacun peut descendre de 2 niveaux.

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

Intuitivement:

"la complexité devrait être O (nLog n)... pour chaque élément que nous "heapify", il a le potentiel d'avoir à filtrer une fois pour chaque niveau pour le tas jusqu'à présent (qui est log n niveaux)."

Pas tout à fait. Votre logique ne produit pas une limite étroite-elle surestime la complexité de chaque heapify. Si elle est construite de bas en haut, l'insertion (heapify) peut être bien inférieure à O(log(n)). Le processus est le suivant:

( Étape 1 ) L' les premiers éléments n/2 vont sur la rangée du bas du tas. h=0, donc heapify n'est pas nécessaire.

( Étape 2 ) les éléments n/22 suivants vont sur la rangée 1 à partir du bas. h=1, heapify filtres 1 niveau vers le bas.

( Étape , je ) les éléments n/2i suivants vont dans la rangée i en haut à partir du bas. h=i, heapify filtres i niveaux vers le bas.

( Étape log(n) ) La dernière n/2log2(n) = 1 élément va à la ligne log(n) par le bas. h=log(n), heapify filtres log(n) niveaux vers le bas.

Notez: {[35] } qu'après la première étape, {[13] } des éléments (n/2) sont déjà dans le tas, et nous n'avons même pas besoin d'appeler heapify une fois. Notez également que seul un seul élément, la racine, encourt la complexité log(n) complète.

Théoriquement:

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

En hauteur i, nous avons montré (ci-dessus) qu'il y aura des éléments n/2i+1 qui doivent appeler heapify, et nous savons que heapify à la hauteur i est O(i). Cela donne:

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étrique bien connue:

Enfin, brancher x = 1/2 dans l'équation ci-dessus donne 2. Brancher ceci dans la première équation donne:

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 plusieurs éléments. 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 "heapify" 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'arbre, en échangeant parent et enfant nœuds jusqu'à ce que les conditions de tas soient remplies.

Lors de la construction d'un tas, disons que vous adoptez 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 de tas. Si, par conséquent, les feuilles incluses dans le tas gratuitement. C'est parce qu'ils n'ont pas d'enfants.
2. en se déplaçant vers le haut, le pire des cas pour le nœud juste au-dessus des feuilles serait 1 comparaison (au maximum, ils seraient comparés à une seule génération d'enfants)
3. aller plus loin en haut, leurs parents immédiats peuvent au maximum être comparés à deux générations d'enfants.
4. en continuant dans la même direction, vous aurez 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 sur 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 nous le savons, la hauteur d'un segment est log(n), où n est le nombre total d'éléments.Permet de la représenter comme h
   Lorsque nous effectuons une opération heapify, les éléments du dernier niveau ( h) ne bougeront même pas d'une seule étape.
, Le nombre d'éléments à l'avant-dernier niveau(h-1) est 2^h-1 et ils peuvent se déplacer à max 1 niveau(cours de heapify).
de Même, pour les je^th, niveau que nous avons 2^j' les éléments qui peuvent se déplacer d' h-i positions.

, par conséquent, nombre total de coups=S= 2^h*0+2^h-1*1+2^h-2*2+...2⁰*h

S=2^h{1/2 + 2/2²+ 3/2³+ ... 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³+ ... h/2^h+1} -------------------------------------------------2
en soustrayant l'équation 2 à partir de 1 donne
                                               S/2=2^h{1/2+1/2²+ 1/2³+ ...+1/2^h+ h/2^h+1}
                                               S=2^h+1{1/2+1/2²+ 1/2³+ ...+1/2^h+ h/2^h+1}
maintenant 1/2+1/2²+ 1/2³+ ...+1/2^h est la diminution de GP dont la somme est inférieure à 1 (lorsque h tend vers l'infini, la somme tend vers 1). Dans une analyse plus approfondie, prenons une limite supérieure sur la somme qui est 1.
Cela donne S=2^h+1{1+h/2^h+1}
=2^h+1+h
~2^h+h
comme h=log(n), 2^h=n

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

En cas de construction du tas, nous partons de la hauteur, logn -1 (où logn est la hauteur de l'arbre de N éléments). Pour chaque élément présent à la hauteur 'h' , nous allons à max jusqu'à (logn-h) Hauteur vers le bas.

    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!))

Par approximation d'étourneau, n! =~ O(n^(n + O(1))), donc T =~ O(nlog(n))

J'espère que cela aide, la manière optimale O(n) utilise l'algorithme de tas de construction pour un ensemble donné (l'ordre n'a pas d'importance).

@bcorso a déjà démontré la preuve de l'analyse de complexité. Mais pour ceux qui apprennent encore l'analyse de la complexité, j'ai ceci à ajouter:

La base de votre erreur initiale 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 lors de l'insertion.

Dans le contexte de l'insertion de n objets dans un tas, la complexité de la ième insertion est O (log n_i) où n_i est la taille du tas comme à l'insertion I. seule la dernière insertion a une complexité de O (log n).

J'aime beaucoup les explications de Jeremy west.... une autre approche qui est vraiment facile à comprendre est donnée ici http://courses.washington.edu/css343/zander/NotesProbs/heapcomplexity

Depuis, buildheap depends en utilisant dépend de heapify et shiftdown approche est utilisée qui dépend de la somme des hauteurs de tous les nœuds. Donc, pour trouver la somme de la hauteur des nœuds qui est donnée par S = somme de i = 0 à i = h (2^i*(h-i)), où h = logn est la hauteur de la arbre la résolution de s, on obtient s = 2^(h+1) - 1 - (h+1) depuis, n = 2^(h+1) - 1 s = n - h - 1 = n - logn - 1 s = O(n), et donc la complexité de buildheap est O(n).

" la limite temporelle linéaire du tas de construction, peut être affichée en calculant la somme des hauteurs de tous les nœuds du tas, qui est le nombre maximum de lignes pointillées. Pour le parfait arbre binaire de hauteur h contenant N = 2^(h+1) – 1 nœuds, la somme des hauteurs des nœuds est N – H – 1. Il est donc O(N)."

Fondamentalement, le travail est effectué uniquement sur les nœuds non-feuilles lors de la construction d'un tas...et le travail effectué est la quantité d'échange vers le bas pour satisfaire tas condition...in d'autres termes (dans le pire des cas), la quantité est proportionnelle à la hauteur du nœud...dans l'ensemble de la complexité du problème est proportionnelle à la somme des hauteurs de tous les non-nœuds feuilles..qui est (2^h + 1-1)-h-1=n-h-1= O(n)

La Preuve de O(n)

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

Pensez que vous faites une erreur. Jetez un oeil à ceci: http://golang.org/pkg/container/heap / Construire un tas n'est pas O(n). Cependant, l'insertion est O (lg (n). Je suppose que l'initialisation est O (n) Si vous définissez une taille de tas b / c, le tas doit allouer de l'espace et configurer la structure de données. Si vous avez n éléments à mettre dans le tas alors oui, chaque insert est lg(n) et il y a n éléments, donc vous obtenez n*lg (n) Comme indiqué