Jak zbudowanie sterty może być złożonością czasową O (n)?

494

Czy ktoś może wyjaśnić, w jaki sposób budowanie sterty może być złożonością O (n)?

Wstawianie elementu do sterty jest O(log n), a wstawianie jest powtarzane n / 2 razy (pozostałe są liśćmi i nie mogą naruszać właściwości sterty). To oznacza, że ​​złożoność powinna być O(n log n), jak sądzę.

Innymi słowy, dla każdego elementu, który „stertyzujemy”, może on wymagać odfiltrowania raz dla każdego poziomu stosu do tej pory (czyli poziomów log n).

czego mi brakuje?

GBa
źródło
co dokładnie rozumiesz przez „budowanie” stosu?
mfrankli
Tak jak w przypadku rozsypiska, weź nieposortowaną tablicę i odfiltruj każdy górny element, aż będzie zgodny z zasadami stosu
GBa
2
Jedyne, co mogłem znaleźć, to ten link: złożoność Buildheap wydaje się wynosić Θ (n lg n) - n połączeń do Heapify kosztem Θ (lg n) za połączenie, ale ten wynik można poprawić do Θ (n) cs.txstate.edu/~ch04/webtest/teaching/courses/5329/lectures/...
GBa
2
@Gba obejrzyj ten film z MIT: Dobrze wyjaśnia, w jaki sposób otrzymujemy O (n), z odrobiną matematyki youtube.com/watch?v=B7hVxCmfPtM
CodeShadow
2
Bezpośredni link do @CodeShadow wyjaśnienie wymienić: youtu.be/B7hVxCmfPtM?t=41m21s
SHA1

Odpowiedzi:

435

Myślę, że w tym temacie jest kilka pytań:

  • Jak wdrożyć, buildHeapaby działało w czasie O (n) ?
  • Jak pokazać, że buildHeapdziała w czasie O (n), gdy jest poprawnie zaimplementowany?
  • Dlaczego ta sama logika nie działa, aby sortowanie sterty działało w czasie O (n) zamiast O (n log n) ?

Jak wdrożyć, buildHeapaby działało w czasie O (n) ?

Często odpowiedzi na te pytania koncentrują się na różnicy między siftUpi siftDown. Właściwy wybór między siftUpi siftDownjest krytyczny dla uzyskania wydajności O (n)buildHeap , ale nie robi nic, aby pomóc zrozumieć różnicę pomiędzy buildHeapi heapSortogólnie. Rzeczywiście, odpowiednie implementacje obu buildHeapi heapSortbędą korzystać tylkosiftDown . Ta siftUpoperacja jest potrzebna tylko do wstawiania do istniejącej sterty, więc może być wykorzystana do zaimplementowania kolejki priorytetowej przy użyciu na przykład sterty binarnej.

Napisałem to, aby opisać, jak działa maksymalna sterty. Jest to typ sterty zwykle używany do sortowania sterty lub do kolejki priorytetowej, w której wyższe wartości wskazują wyższy priorytet. Przydatna jest również sterta min; na przykład podczas wyszukiwania elementów z kluczami całkowitymi w porządku rosnącym lub ciągami znaków w kolejności alfabetycznej. Zasady są dokładnie takie same; wystarczy zmienić kolejność sortowania.

Właściwość sterta określa, że ​​każdy węzeł w stercie binarnym musi być co najmniej tak duży, jak oba jego elementy potomne. W szczególności oznacza to, że największy element na stosie znajduje się w katalogu głównym. Przesiewanie w dół i przesiewanie w górę to w zasadzie ta sama operacja w przeciwnych kierunkach: przesuń naruszający węzeł, aż spełni właściwości sterty:

  • siftDown zamienia zbyt mały węzeł z jego największym dzieckiem (przesuwając go w dół), aż będzie co najmniej tak duży, jak oba węzły pod nim.
  • siftUp zamienia węzeł, który jest zbyt duży z rodzicem (tym samym przesuwając go w górę), aż nie będzie większy niż węzeł nad nim.

Liczba operacji wymaganych siftDowni siftUpjest proporcjonalna do odległości, jaką może pokonać węzeł. Ponieważ siftDownjest to odległość do dolnej części drzewa, więc siftDownjest kosztowna dla węzłów na szczycie drzewa. Dzięki siftUp, praca jest proporcjonalna do odległości do szczytu drzewa, więc siftUpjest kosztowna dla węzłów na dole drzewa. Chociaż obie operacje są w najgorszym przypadku O (log n) , w stercie tylko jeden węzeł znajduje się na górze, podczas gdy połowa węzłów leży na dolnej warstwie. Nie powinno więc dziwić, że gdybyśmy musieli zastosować operację do każdego węzła, wolelibyśmy siftDownwięcej siftUp.

buildHeapFunkcja przyjmuje tablicę nieposortowane przedmiotów i przenosi je do momentu spełnienia wszystkich właściwość stos, tworząc w ten sposób poprawny sterty. Istnieją dwa podejścia można by przyjąć za buildHeapwykorzystaniem siftUpi siftDownoperacje Opisaliśmy.

  1. Rozpocznij na górze stosu (na początku tablicy) i wywołaj siftUpkażdy element. Na każdym etapie poprzednio przesiane elementy (elementy przed bieżącym elementem w tablicy) tworzą prawidłową stertę, a przesiewanie następnego elementu w górę umieszcza go w prawidłowej pozycji na stercie. Po przesianiu każdego węzła wszystkie elementy spełniają właściwość sterty.

  2. Lub idź w przeciwnym kierunku: zacznij od końca tablicy i cofnij się do przodu. Przy każdej iteracji przesiewasz przedmiot w dół, aż znajdzie się we właściwej lokalizacji.

Które wdrożenie buildHeapjest bardziej wydajne?

Oba te rozwiązania wygenerują prawidłową stertę. Nic dziwnego, że bardziej wydajna jest druga operacja siftDown.

Niech h = log n reprezentuje wysokość stosu. Praca wymagana do tego siftDownpodejścia jest sumą

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

Każdy termin w sumie ma maksymalną odległość, którą musi przesunąć węzeł na danej wysokości (zero dla dolnej warstwy, h dla korzenia) pomnożony przez liczbę węzłów na tej wysokości. Natomiast suma za wywołanie siftUpw każdym węźle wynosi

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

Powinno być jasne, że druga suma jest większa. Sam pierwszy termin to hn / 2 = 1/2 n log n , więc to podejście ma w najlepszym razie złożoność O (n log n) .

Jak udowodnimy, że suma dla tego siftDownpodejścia jest rzeczywiście O (n) ?

Jedną z metod (istnieją inne analizy, które również działają) jest przekształcenie skończonej sumy w szereg nieskończony, a następnie użycie szeregu Taylora. Możemy zignorować pierwszy termin, który wynosi zero:

Seria Taylora dla złożoności buildHeap

Jeśli nie masz pewności, dlaczego każdy z tych kroków działa, oto uzasadnienie tego procesu w słowach:

  • Wszystkie warunki są dodatnie, więc suma skończona musi być mniejsza niż suma nieskończona.
  • Szereg jest równy szeregowi mocy oszacowanemu przy x = 1/2 .
  • Ta seria mocy jest równa (stałemu czasowi) pochodnej szeregu Taylora dla f (x) = 1 / (1-x) .
  • x = 1/2 mieści się w przedziale zbieżności tej serii Taylora.
  • Dlatego możemy zamienić szereg Taylora na 1 / (1-x) , różnicować i oceniać, aby znaleźć wartość szeregu nieskończonego.

Ponieważ suma nieskończona wynosi dokładnie n , dochodzimy do wniosku, że suma skończona nie jest większa, a zatem wynosi O (n) .

Dlaczego sortowanie sterty wymaga czasu O (n log n) ?

Jeśli możliwe jest uruchomienie buildHeapw czasie liniowym, dlaczego sortowanie sterty wymaga czasu O (n log n) ? Sortowanie sterty składa się z dwóch etapów. Najpierw wywołujemy buildHeaptablicę, która wymaga O (n) czasu, jeśli jest zaimplementowana optymalnie. Następnym etapem jest wielokrotne usuwanie największego elementu ze sterty i umieszczanie go na końcu tablicy. Ponieważ usuwamy element ze sterty, tuż za końcem sterty zawsze jest otwarte miejsce, w którym możemy przechowywać przedmiot. Tak więc sortowanie sterty osiąga uporządkowany porządek poprzez sukcesywne usuwanie następnego największego przedmiotu i umieszczanie go w tablicy, zaczynając od ostatniej pozycji i przesuwając się do przodu. To złożoność tej ostatniej części dominuje w rodzaju sterty. Pętla wygląda następująco:

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

Oczywiście, pętla działa O (n) razy ( n - 1, by być dokładnym, ostatni element jest już na miejscu). Złożoność deleteMaxstosu wynosi O (log n) . Zwykle jest to realizowane przez usunięcie korzenia (największego elementu pozostawionego na stercie) i zastąpienie go ostatnim elementem na stercie, który jest liściem, a zatem jednym z najmniejszych elementów. Ten nowy root prawie na pewno naruszy właściwość sterty, więc musisz zadzwonić, siftDowndopóki nie przeniesiesz go z powrotem do akceptowalnej pozycji. To również powoduje przeniesienie następnego największego przedmiotu do korzenia. Zauważ, że w przeciwieństwie do tego, buildHeapgdzie w przypadku większości węzłów wzywamy siftDownod dołu drzewa, teraz wzywamy siftDownod góry drzewa podczas każdej iteracji!Chociaż drzewo kurczy się, nie kurczy się wystarczająco szybko : wysokość drzewa pozostaje stała, dopóki nie usuniesz pierwszej połowy węzłów (po całkowitym usunięciu dolnej warstwy). Następnie przez następny kwartał wysokość wynosi h - 1 . Tak więc całkowita praca dla tego drugiego etapu wynosi

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

Zwróć uwagę na przełącznik: teraz zerowy przypadek roboczy odpowiada jednemu węzłowi, a przypadek roboczy h odpowiada połowie węzłów. Ta suma wynosi O (n log n), podobnie jak nieefektywna wersja buildHeaptego jest implementowana za pomocą siftUp. Ale w tym przypadku nie mamy wyboru, ponieważ próbujemy sortować i wymagamy następnego następnego największego elementu do usunięcia.

Podsumowując, praca dla sortowania sterty jest sumą dwóch etapów: O (n) czas na buildHeap i O (n log n) do usunięcia każdego węzła w kolejności , więc złożoność wynosi O (n log n) . Możesz udowodnić (korzystając z niektórych pomysłów z teorii informacji), że dla sortowania opartego na porównaniu O (n log n) jest najlepszym, na co możesz liczyć, więc nie ma powodu, aby być rozczarowanym tym lub oczekiwać, że sortowanie sterty pozwoli osiągnąć O (n) czas, który buildHeapspełnia.

Jeremy West
źródło
2
Zredagowałem swoją odpowiedź, aby użyć maksymalnej sterty, ponieważ wydaje się, że większość innych osób odnosi się do tego i jest to najlepszy wybór do sortowania sterty.
Jeremy West,
28
To intuicyjnie wyjaśniło mi: „tylko jeden węzeł znajduje się u góry, podczas gdy połowa węzłów leży w dolnej warstwie. Nie powinno więc dziwić, że gdybyśmy musieli zastosować operację do każdego węzła, wolę siftDown niż siftUp. ”
Vicky Chijwani,
3
@JeremyWest „Jednym z nich jest rozpoczęcie na szczycie stosu (początek tablicy) i wywołanie siftUp na każdym elemencie”. - Czy chciałeś zacząć od dołu stosu?
aste123
4
@ aste123 Nie, jest poprawny jak napisano. Pomysł polega na utrzymaniu bariery między częścią tablicy, która spełnia właściwość sterty, a nieposortowaną częścią tablicy. Albo zaczynasz od początku, przechodząc do przodu i wzywając siftUpkażdy element, albo zaczynasz od końca, cofając się i dzwoniąc siftDown. Bez względu na to, które podejście wybierzesz, wybierasz następny element w nieposortowanej części tablicy i wykonujesz odpowiednią operację, aby przenieść go do prawidłowej pozycji w uporządkowanej części tablicy. Jedyną różnicą jest wydajność.
Jeremy West,
2
To najlepsza odpowiedź, jaką kiedykolwiek spotkałem na każde pytanie na świecie. To było tak dobrze wyjaśnione, pomyślałem, że to naprawdę możliwe ... wielkie dzięki.
HARSHIL JAIN,
314

Twoja analiza jest poprawna. Jednak nie jest ciasno.

Nie jest łatwo wyjaśnić, dlaczego budowanie sterty jest operacją liniową, lepiej ją przeczytaj.

Wielki analiza algorytmu można zobaczyć tutaj .


Główną ideą jest to, że w build_heapalgorytmie rzeczywisty heapifykoszt nie O(log n)dotyczy wszystkich elementów.

Po heapifywywołaniu czas działania zależy od tego, jak daleko element może się przesunąć w dół drzewa przed zakończeniem procesu. Innymi słowy, zależy to od wysokości elementu w stercie. W najgorszym przypadku element może spaść aż do poziomu liścia.

Policzmy pracę wykonaną poziom po poziomie.

Na najniższym poziomie są 2^(h)węzły, ale nie wzywamy heapifyżadnego z nich, więc praca wynosi 0. Na następnym poziomie są 2^(h − 1)węzły i każdy może przejść w dół o 1 poziom. Na 3. poziomie od dołu znajdują się 2^(h − 2)węzły, z których każdy może przejść w dół o 2 poziomy.

Jak widać, nie wszystkie operacje rozsypywania są O(log n), dlatego otrzymujesz O(n).

emre nevayeshirazi
źródło
17
To świetne wytłumaczenie ... ale dlaczego tak się dzieje, że sortowanie sterty działa w O (n log n). Dlaczego to samo rozumowanie nie dotyczy sortowania stosów?
hba
49
@hba Myślę, że odpowiedź na twoje pytanie polega na zrozumieniu tego obrazu z tego artykułu . Heapifyjest O(n)po zakończeniu, siftDownale O(n log n)po zakończeniu siftUp. Rzeczywiste sortowanie (wyciąganie przedmiotów ze stosu jeden po drugim) musi być siftUpzatem wykonane O(n log n).
The111
3
Bardzo podoba mi się intuicyjne wyjaśnienie twojego dokumentu zewnętrznego na dole.
Lukas Greblikas
1
@hba Poniższa odpowiedź Jeremy'ego Westa odpowiada na twoje pytanie w bardziej szczegółowy, łatwy do zrozumienia sposób, wyjaśniając tutaj odpowiedź The111 na komentarz.
cellepo
Pytanie. Wydaje mi się, że porównania # wykonane dla węzła na wysokości iod dołu drzewa wysokości h muszą również dokonać 2* log(h-i)porównań i należy je również uwzględnić @ The111. Co myślisz?
Sid
94

Intuicyjnie:

„Złożoność powinna wynosić O (nLog n) ... dla każdego elementu, który„ stertyzujemy ”, może potencjalnie wymagać odfiltrowania raz dla każdego poziomu stosu do tej pory (czyli poziomów log n).”

Nie do końca. Twoja logika nie tworzy ścisłej więzi - przesadza z oszacowaniem złożoności każdego heapify. W przypadku budowania od podstaw, wstawianie (heapify) może być znacznie mniejsze niż O(log(n)). Proces przebiega następująco:

(Krok 1) Pierwsze n/2elementy trafiają do dolnego rzędu stosu. h=0, więc heapify nie jest potrzebne.

(Krok 2) Następne elementy idą w rzędzie 1 w górę od dołu. , heapify filtry o 1 poziom w dół.n/22h=1

(Krok i ) Następne elementy idą w rzędzie w górę od dołu. obniża poziomy filtrów .n/2iih=ii

(Krok dziennika (n) ) Ostatni element idzie w rzędzie w górę od dołu. obniża poziomy filtrów .n/2log2(n) = 1log(n)h=log(n)log(n)

ZAUWAŻ: że po pierwszym kroku 1/2elementy (n/2)są już w stercie i nie musieliśmy nawet wywoływać jednorazowo wezwania. Zauważ też, że tylko jeden element, rdzeń, w rzeczywistości powoduje pełną log(n)złożoność.


Teoretycznie:

Całkowitą Nliczbę kroków do zbudowania sterty wielkości nmożna zapisać matematycznie.

Na wysokości ipokazaliśmy (powyżej), że będą elementy, które będą musiały wywołać heapify, i wiemy, że heapify na wysokości to . To daje:n/2i+1iO(i)

wprowadź opis zdjęcia tutaj

Rozwiązanie ostatniego sumowania można znaleźć, biorąc pochodną obu stron znanego równania szeregów geometrycznych:

wprowadź opis zdjęcia tutaj

Wreszcie podłączenie x = 1/2do powyższego równania daje wynik 2. Podłączenie tego do pierwszego równania daje:

wprowadź opis zdjęcia tutaj

Zatem łączna liczba kroków ma rozmiar O(n)

bcorso
źródło
35

Byłoby O (n log n), jeśli zbudowałeś stertę przez wielokrotne wstawianie elementów. Możesz jednak wydajniej utworzyć nową stertę, wstawiając elementy w dowolnej kolejności, a następnie stosując algorytm do „stertyfikowania” ich we właściwej kolejności (w zależności od rodzaju sterty, oczywiście).

Zobacz http://en.wikipedia.org/wiki/Binary_heap „Budowanie sterty” dla przykładu. W tym przypadku zasadniczo pracujesz od najniższego poziomu drzewa, zamieniając węzły nadrzędne i potomne, dopóki warunki sterty nie zostaną spełnione.

mike__t
źródło
12

Jest już kilka świetnych odpowiedzi, ale chciałbym dodać trochę wizualnego wyjaśnienia

wprowadź opis zdjęcia tutaj

Teraz spójrz na obrazek, są
n/2^1 zielone węzły o wysokości 0 (tutaj 23/2 = 12)
n/2^2 czerwone węzły o wysokości 1 (tutaj 23/4 = 6)
n/2^3 niebieski węzeł o wysokości 2 (tutaj 23/8 = 3)
n/2^4 fioletowe węzły o wysokości 3 (tutaj 23/16 = 2),
więc są n/2^(h+1)węzły dla wysokości h
Aby znaleźć złożoność czasu, policzmy ilość pracy wykonanej lub max liczbę iteracji wykonanych przez każdy węzeł,
teraz można zauważyć, że każdy węzeł może wykonaj (atmost) iteracje == wysokość węzła

Green  = n/2^1 * 0 (no iterations since no children)  
red    = n/2^2 * 1 (heapify will perform atmost one swap for each red node)  
blue   = n/2^3 * 2 (heapify will perform atmost two swaps for each blue node)  
purple = n/2^4 * 3 (heapify will perform atmost three swaps for each purple node)   

więc dla wszystkich węzłów o wysokości h maksymalna wykonana praca wynosi n / 2 ^ (h + 1) * h

Teraz wykonano całą pracę

->(n/2^1 * 0) + (n/2^2 * 1)+ (n/2^3 * 2) + (n/2^4 * 3) +...+ (n/2^(h+1) * h)  
-> n * ( 0 + 1/4 + 2/8 + 3/16 +...+ h/2^(h+1) ) 

teraz dla dowolnej wartości h , sekwencji

-> ( 0 + 1/4 + 2/8 + 3/16 +...+ h/2^(h+1) ) 

nigdy nie przekroczy 1
Tak więc złożoność czasowa nigdy nie przekroczy O (n) dla budowy stosu

Julkar9
źródło
7

Jak wiemy, wysokość stosu to log (n) , gdzie n to całkowita liczba elementów.    Niech to reprezentuje jako h.
Kiedy wykonujemy operację heapify, elementy na ostatnim poziomie ( h ) nie poruszą się nawet krok.
   Liczba elementów na drugim ostatnim poziomie ( h-1 ) wynosi 2 h-1 i mogą się one poruszać na maksymalnie 1 poziomie (podczas heapify).
   Podobnie dla ı TH , poziom mamy 2 i elementów, które mogą się poruszać hi pozycji.

Dlatego łączna liczba ruchów = S = 2 h * 0 + 2 h-1 * 1 + 2 h-2 * 2 + ... 2 0 * h

                                               S = 2 godz. {1/2 + 2/2 2 + 3/2 3 + ... h / 2 godz. } ----------------------- -------------------------- 1
to jest seria AGP , aby rozwiązać ten podział, podziel obie strony przez 2
                                               S / 2 = 2 h {1/2 2 + 2/2 3 + ... h / 2 h + 1 } --------------------------------- ---------------- 2
odjęcie równania 2 od 1 daje
                                               S / 2 = 2 h { 1/2 + 1/2 2 + 1/2 3 + ... + 1 / 2 godz. + Godz. / 2 godz. + 1 }
                                                S = 2 h + 1 { 1/2 + 1/2 2 + 1/2 3 + ... +1/2 h + h / 2 h + 1 }
się 1/2 + 1/2 2 + 1/2 3 + ... + 1/2 h zmniejsza GP, którego suma jest mniejsza niż 1 (gdy h dąży do nieskończoności, suma dąży do 1). W dalszej analizie, weźmy górną granicę sumy, która wynosi 1.
To daje S = 2 h + 1 {1 + h / 2 h + 1 }
                    = 2 h + 1 + h
                    ~ 2 h + h
as h = log (n) , 2 godz. = n

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

Tanuj Yadav
źródło
6

Budując stertę, powiedzmy, że stosujesz podejście oddolne.

  1. Bierzesz każdy element i porównujesz go z jego dziećmi, aby sprawdzić, czy para jest zgodna z regułami sterty. Dlatego liście dołączane są do kupy za darmo. To dlatego, że nie mają dzieci.
  2. Idąc w górę, najgorszym scenariuszem dla węzła tuż nad liśćmi byłoby 1 porównanie (przy maksimum byłyby one porównywane tylko z jednym pokoleniem dzieci)
  3. Idąc dalej, ich najbliżsi rodzice mogą być maksymalnie porównani z dwoma pokoleniami dzieci.
  4. Kontynuując w tym samym kierunku, będziesz mieć log (n) porównania dla katalogu głównego w najgorszym przypadku. i log (n) -1 dla jego bezpośrednich potomków, log (n) -2 dla ich bezpośrednich potomków i tak dalej.
  5. Podsumowując, otrzymujesz coś w rodzaju log (n) + {log (n) -1} * 2 + {log (n) -2} * 4 + ..... + 1 * 2 ^ {( logn) -1}, który jest niczym innym jak O (n).
Jones
źródło
2

W przypadku budowy hałdy zaczynamy od wysokości, logn -1 (gdzie logn jest wysokością drzewa n elementów). Dla każdego elementu obecnego na wysokości „h” przechodzimy do maksymalnej wysokości (logn-h) wysokości w dół.

    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)
Kartik Goyal
źródło
1

Kolejne wstawki można opisać przez:

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

n! =~ O(n^(n + O(1)))Dlatego przybliżając szpakT =~ O(nlog(n))

Mam nadzieję, że to pomaga, optymalnym sposobem O(n)jest użycie algorytmu budowania sterty dla danego zestawu (kolejność nie ma znaczenia).

Tomer Shalev
źródło
1

Zasadniczo praca jest wykonywana tylko na węzłach innych niż liście podczas budowania stosu ... a wykonana praca to ilość zamiany w dół, aby spełnić warunek stosu ... innymi słowy (w najgorszym przypadku) ilość jest proporcjonalna do wysokości węzła ... w sumie złożoność problemu jest proporcjonalna do sumy wysokości wszystkich nie-liściowych węzłów .. którym jest (2 ^ h + 1 - 1) -h-1 = nh-1 = Na)

Shubham Jindal
źródło
1

@bcorso pokazał już dowód analizy złożoności. Ale ze względu na osoby wciąż uczące się analizy złożoności muszę dodać:

Podstawa twojego pierwotnego błędu wynika z błędnej interpretacji znaczenia stwierdzenia: „wstawienie do stosu zajmuje czas O (log n)”. Wstawianie do stosu jest rzeczywiście O (log n), ale musisz rozpoznać, że n jest rozmiarem stosu podczas wstawiania .

W kontekście wstawiania n obiektów do stosu złożoność i-tego wstawienia wynosi O (log n_i), gdzie n_i jest rozmiarem stosu jak przy wstawianiu i. Tylko ostatnie wstawienie ma złożoność O (log n).

N.Vegeta
źródło
1

Załóżmy, że masz N elementów na stosie. Wtedy jego wysokość wynosiłaby Log (N)

Teraz chcesz wstawić inny element, to złożoność byłoby: log (N) , musimy porównać całą drogę UP do korzenia.

Teraz masz N + 1 elementów i wysokość = Log (N + 1)

Za pomocą techniki indukcyjnej można udowodnić, że złożoność wstawienia byłaby ∑logi .

Teraz używa

log a + log b = log ab

Upraszcza to: ∑logi = log (n!)

czyli tak naprawdę O (NlogN)

Ale

robimy tutaj coś złego, ponieważ we wszystkich przypadkach nie sięgamy do szczytu. Dlatego podczas wykonywania większości przypadków możemy się przekonać, że nie idziemy nawet w połowie wysokości drzewa. Skąd ta granica może być zoptymalizowana, aby mieć jeszcze ściślejszą granicę, używając matematyki podanej w odpowiedziach powyżej.

Ta realizacja przyszła do mnie po szczegółach i eksperymentach na hałdach.

Fooo
źródło
0

Naprawdę podoba mi się wyjaśnienie Jeremy'ego Westa .... inne podejście, które jest naprawdę łatwe do zrozumienia, znajduje się tutaj http://courses.washington.edu/css343/zander/NotesProbs/heapcomplexity

ponieważ budowanie zależy od użycia zależy od stosu i stosuje się podejście zmniejszające, które zależy od sumy wysokości wszystkich węzłów. Tak więc, aby znaleźć sumę wysokości węzłów, która jest dana przez S = sumowanie od i = 0 do i = h z (2 ^ i * (hi)), gdzie h = logn jest wysokością rozwiązania drzewa s, otrzymujemy s = 2 ^ (h + 1) - 1 - (h + 1), ponieważ n = 2 ^ (h + 1) - 1 s = n - h - 1 = n- logn - 1 s = O (n), i tak złożoność zestawienia kompilacji wynosi O (n).

Nitish Jain
źródło
0

„Liniową granicę czasową kompilacji Sterty można pokazać, obliczając sumę wysokości wszystkich węzłów w stercie, która jest maksymalną liczbą linii przerywanych. Dla idealnego drzewa binarnego wysokości h zawierającego N = 2 ^ ( h + 1) - 1 węzły, suma wysokości węzłów wynosi N - H - 1. Zatem jest to O (N). ”

sec3
źródło
0

Dowód O (n)

Dowód nie jest wyszukany i dość prosty, udowodniłem tylko, że jest to pełne drzewo binarne, wynik można uogólnić dla pełnego drzewa binarnego.

Yi Y
źródło
0

Czas wykonywania kompilacji sterty uzyskujemy, ustalając maksymalny ruch, jaki może podjąć każdy węzeł. Musimy więc wiedzieć, ile węzłów znajduje się w każdym rzędzie i jak daleko od nich może przejść każdy węzeł.

Zaczynając od węzła głównego, każdy następny rząd ma dwa razy więcej węzłów niż poprzedni, więc odpowiadając, jak często możemy podwoić liczbę węzłów, dopóki nie zostanie nam żaden węzeł, otrzymamy wysokość drzewa. Lub w kategoriach matematycznych wysokość drzewa wynosi log2 (n), gdzie n jest długością tablicy.

Aby obliczyć węzły w jednym rzędzie, zaczynamy od tyłu, wiemy, że n / 2 węzłów znajduje się na dole, więc dzieląc przez 2, otrzymujemy poprzedni wiersz i tak dalej.

Na tej podstawie otrzymujemy wzór na podejście Siftdown: (0 * n / 2) + (1 * n / 4) + (2 * n / 8) + ... + (log2 (n) * 1)

Termin w ostatnim nawiasie to wysokość drzewa pomnożona przez jeden węzeł znajdujący się u nasady, termin w pierwszym nawiasie to wszystkie węzły w dolnym rzędzie pomnożone przez długość, jaką mogą przebyć, 0. Ta sama formuła w smart: wprowadź opis zdjęcia tutaj

Matematyka

Przywracając n mamy 2 * n, 2 można odrzucić, ponieważ jest to ciągłe i tada mamy najgorszy czas działania podejścia Siftdown: n.

Max Tromp
źródło
-6

myślę, że popełniasz błąd. Spójrz na to: http://golang.org/pkg/container/heap/ Budowanie sterty to nie O (n). Jednak wstawianie to O (lg (n). Zakładam, że inicjalizacja to O (n), jeśli ustawisz rozmiar sterty b / c, sterty muszą przydzielić miejsce i skonfigurować strukturę danych. Jeśli masz n elementów do umieszczenia do stosu, a następnie tak, każda wstawka jest lg (n) i jest n elementów, więc dostajesz n * lg (n), jak podano

Mike Schachter
źródło
2
nie, nie jest ciasno. dokładniejsza analiza wydajności sterty kompilacji O (n)
emre nevayeshirazi
wygląda na to, że to oszacowanie. Cytat w artykule, do którego się odwołuje, brzmi: „Intuicja polega na tym, że większość wezwań do rozsypywania jest na bardzo krótkich hałdach”. To jednak powoduje pewne założenia. Prawdopodobnie w przypadku dużej sterty najgorszym scenariuszem byłoby nadal O (n * lg (n)), nawet jeśli zwykle można zbliżyć się do O (n). Ale mogę się mylić
Mike Schachter
Tak, to także moja intuicyjna odpowiedź, ale odniesienia takie jak wikipedia stwierdzają: „Sterty z n elementami można budować oddolnie w O (n)”.
GBa
1
Myślałem o w pełni posortowanej strukturze danych. Zapomniałem konkretnych właściwości sterty.
Mike Schachter