Kaip galiu sukurti O (n) laiko komplekso krūva?

Ar kas nors gali paaiškinti, kaip sukurti O (n) sudėtingumo krūva?

Įterpia elementą į O(log n) krūvą ir įterpimas kartojamas n / 2 kartus (likusi dalis yra lapai ir negali pažeisti krūvos turto). Taigi tai reiškia, kad sudėtingumas turėtų būti O(n log n) , manau.

Kitaip tariant, kiekvienam elementui, kurį mes „surenkame“, jis gali filtruoti vieną kartą kiekvienam lygiui iki šiol (tai yra log n lygiai).

Kas man trūksta?

338
18 марта '12 в 6:15 2012-03-18 06:15 GBa yra nustatytas kovo 18, 12, 12:15 2012-03-18 06:15
@ 15 atsakymų

Manau, kad šioje temoje yra palaidoti keli klausimai:

  • Kaip įdiegiate „buildHeap“, kad jis vykdytų O (n) laikus?
  • Kaip parodyti, kad „buildHeap“ darbai atliekami O (N) laiku, kai jie įgyvendinami teisingai?
  • Kodėl ta pati logika neveikia taip, kad krūva būtų atliekama O (n), o ne O (n log n)?

Dažnai atsakymai į šiuos klausimus sutelkiami į skirtumą tarp siftUp ir siftDown . Tinkamas pasirinkimas tarp „ siftUp ir „ siftDown labai svarbus norint gauti „O“ (n) buildHeapbuildHeap , tačiau tai nepadeda suprasti skirtumo tarp „ buildHeap ir „ heapSort . Iš tiesų, teisingi ir buildHeap ir „ heapSort bus naudojami tik siftDown . siftUp operacija yra reikalinga tik įterpiant į esamą krūvą, todėl ji bus naudojama, pavyzdžiui, įgyvendinant prioritetinę eilę naudojant dvejetainį krūvą.

Aš tai parašiau, kad apibūdintumėte, kaip veikia maksimalus krūva. Šio tipo krūva paprastai naudojama krūvos rūšiavimui arba prioritetinei eilei, kur aukštesnės vertės nurodo aukštesnį prioritetą. Taip pat naudinga minų krūva; Pvz., kai siunčiami elementai su sveikais skaičiais klavišais didėjančia tvarka arba eilutėmis abėcėlės tvarka. Principai yra tokie patys; tiesiog perjunkite rūšiavimo tvarką.

Krūvos savybė rodo, kad kiekvienas dvejetainio krūvos mazgas turi būti bent tokio paties dydžio kaip ir abu jo elementai. Visų pirma tai reiškia, kad didžiausias krūvos elementas yra šaknis. Atranka ir atranka iš esmės yra ta pati operacija priešingomis kryptimis: perkelkite pažeidžiančią mazgą, kol jis tenkina krūvos turtą:

  • siftDown keičia per mažą mazgą su didžiausiu vaiko mazgu (tokiu būdu perkeliant jį žemyn), kol jis tampa bent toks pat didelis, kaip ir abu mazgai.
  • siftUp pakeičia mazgą, kuris yra per didelis su savo tėvais (taip juda jį aukštyn), kol jis yra didesnis nei mazgas virš jo.

Operacijų, reikalingų siftDown ir siftUp yra proporcingas atstumui, kurį gali pasiekti mazgas. siftDown tai yra atstumas iki medžio apačios, todėl siftDown kelias, esantis mazgų, esančių medžio viršuje. Su siftUp darbas yra proporcingas atstumui iki medžio viršaus, taigi siftUp brangus mazgų, esančių medžio apačioje. Nors blogiausiu atveju abi operacijos yra lygios O (log n), viršuje yra tik vienas mazgas, o pusė mazgų yra žemesniame lygyje. Todėl neturėtų būti pernelyg nustebinti, kad jei kiekvienam mazgų reikia taikyti operaciją, mes norėtume, kad siftDown siftUp .

buildHeap funkcija įgauna nerūšiuotų elementų masyvą ir juos perkelia, kol jie visi patenkins krūvos turtą, taip sukuriant tinkamą krūvą. Yra du būdai, kurie gali būti naudojami siekiant buildHeap naudojant siftUp siftDown operaciją siftUp ir siftDown .

  1. Pradėkite krūvos viršuje (masyvo pradžioje) ir skambinkite siftUp kiekvienam elementui. Kiekviename etape anksčiau nukreipti elementai (elementai prieš dabartinį elementą masyve) sudaro galiojantį krūvą, o kito elemento išsiėmimas įdeda jį į tinkamą vietą krūvoje. Kiekvieną mazgą atsijojus, visi elementai atitinka krūvos savybes.

  2. Arba eikite priešinga kryptimi: pradėkite masyvo pabaigoje ir judėkite pirmyn ir atgal. Kiekviename iteracijoje elementą perkratote tol, kol jis bus tinkama vieta.

Abu šie sprendimai sukurs tinkamą krūvą. Kyla klausimas, kokie įgyvendinimo buildHeap efektyvesni? Nenuostabu, kad tai yra antroji operacija, kurioje naudojama siftDown .

Leiskite h = log n atstovauti krūvos aukštį. siftDown metodui reikalingą darbą lemia suma

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

Kiekvienas terminas sumoje turi maksimalų atstumą, kurį mazgas turės keliauti tam tikru aukščiu (apatinio sluoksnio nulis, h šakniui), padaugintas iš mazgų toje aukštyje. Priešingai, suma, kurią reikia skambinti siftUp kiekviename mazge

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

Turėtų būti aišku, kad antroji suma yra didesnė. Vienas pirmasis terminas yra hn / 2 = 1/2 n log n, taigi šis požiūris geriausiu atveju yra sudėtingas O (n log n). Bet kaip mes galime įrodyti, kad siftDown metodo siftDown iš tikrųjų siftDown O (n)? Vienas iš būdų (yra ir kitų analizių, kurios taip pat veikia) yra baigtinės sumos pavertimas begaline serija ir tada panaudoti Taylor seriją. Mes galime ignoruoti pirmąjį terminą, kuris yra nulis:

2019

11 сент. Jeremy West atsakymas rugsėjo 11 d. 2013-09-11 16:22 '13, 16:22, 2013-09-11 16:22

Jūsų analizė yra teisinga. Tačiau tai nėra sunku.

Tiesą sakant, nėra lengva paaiškinti, kodėl krūvos sukūrimas yra tiesinė operacija, geriau ją perskaityti.

Čia galima pamatyti didelę algoritmo analizę.


Pagrindinė idėja yra ta, kad „ build_heap algoritme faktinė „ heapify nėra lygi O(log n) visiems elementams.

Kai heapify , vykdymo laikas priklauso nuo to, kiek elementas medyje gali judėti tol, kol procesas bus baigtas. Kitaip tariant, tai priklauso nuo elemento aukščio krūvoje. Blogiausiu atveju elementas gali nukristi iki lapo lygio.

Apskaičiuokite atliktą darbą pagal lygį.

Žemiausiame lygyje yra 2^(h) mazgai, bet mes jokiu būdu heapify , todėl darbas yra 0. Kitame lygyje yra 2^(h − 1) mazgai, ir kiekvienas iš jų gali judėti žemyn 1 lygiu. Trečiajame lygyje yra mazgų 2^(h − 2) , o kiekvienas iš jų gali nukristi iki 2 lygių.

Kaip matote, ne visos „ O(log n) operacijos, todėl jūs gaunate O(n) .

285
18 марта '12 в 6:39 2012-03-18 06:39 atsakymas į emre nevayeshirazi kovo 18 d., 12 val. 6:39 2012-03-18 06:39

Aišku:

"Sudėtingumas turi būti O (nLog n) ... kiekvienam elementui, kurį mes" surenkame ", jis turi galimybę filtruoti vieną kartą kiekvienam lygiui iki šiol (tai yra log n lygiai)."

Ne iš tikrųjų. Jūsų logika nesukuria griežto įpareigojimo - ji įvertina kiekvieno iš jų sudėtingumą. Jei pastatytas iš apačios į viršų, „heapify“ gali būti daug mažesnis nei O(log(n)) . Procesas yra toks:

(1 žingsnis) Pirmieji n/2 elementai įveda apatinę krūvos eilutę. h=0 , todėl nereikalaujama.

(2 veiksmas) Šie punktai n/2 2 eina iki 1 eilutės. h=1 , 1 lygio lygis filtruoja.

(i pakopa) Šie n/2 i elementai eina i eilutėje viršutiniame apačioje. h=i , surinkite filtrus žemyn.

(Žingsnis log (n)) Galutinis elementas n/2 log 2 (n) = 1 yra viršutiniame apačioje esančiame eilutėje log(n) . h=log(n) , pašalinkite log(n) filtrus.

PRANEŠIMAS: po pirmojo žingsnio 1/2 elementų (n/2) jau yra krūvoje, ir mes net neturėjome skambinti vienai kartai. Taip pat atkreipkite dėmesį, kad tik vienas elementas, šaknis, iš tikrųjų atlieka visą log(n) sudėtingumą.


Teoriškai:

Galutiniai žingsniai N , sukurti N dydžio krūvą, gali būti parašyti matematiškai.

i mes parodėme (aukščiau), kad bus elementų n/2 i+1 kurie turėtų paskambinti heapify, ir mes žinome, heapify aukštyje i yra O(i) . Ji suteikia:

2019

82
18 авг. bcorso atsakymas 18 rug . 2013-08-18 06:13 '13, 6:13 2013-08-18 06:13

Tai bus O (n log n), jei pastatėte krūvą pakartotinai įterpiant elementus. Tačiau efektyviau galite sukurti naują krūvą, įterpdami elementus į savavališką tvarką ir tada pritaikydami algoritmą juos „surinkti“ teisinga tvarka (priklausomai nuo, žinoma, krūvos tipo).

Pavyzdžiui, žr. Http://en.wikipedia.org/wiki/Binary_heap , „Kupono kūrimas“. Tokiu atveju jūs iš esmės dirbate medžio apačioje, pakeisdami tėvų ir vaikų mazgus, kol bus įvykdytos krūvos sąlygos.

32
18 марта '12 в 6:36 2012-03-18 06:36 atsakymas duotas mike__t kovo 18 d. 12 val. 6:36 2012-03-18 06:36

Kaip žinome, krūvos aukštis yra log (n) , kur n yra bendras elementų skaičius. Jis žymi kaip h
Kai atliekame operacinę operaciją, elementai paskutiniame lygyje ( h ) netaps vienu žingsniu. Elementų skaičius antrame paskutiniame lygyje ( h-1 ) yra 2 h-1 ir jie gali judėti maks. Panašiai, i -ojo lygio , mes turime 2 i, kurie gali perkelti hi pozicijas.

Todėl bendras judesių skaičius = S = 2 h * 0 + 2 h -1 * 1 + 2 h -2 * 2 + ... 2 0 * h

S = 2 val. {1/2 + 2/2 2 + 3/2 3 + ... h / 2 h } ----------------------- ------------------- ------- 1
Tai AGP serija, skirta išspręsti šią problemą abiem pusėms
S / 2 = 2 val. {1/2 2 + 2/2 3 + ... h / 2 h + 1 } ----------------------- -------- ------------------ 2
atimant lygtį 21 , S / 2 = 2 val. {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 }
dabar 1/2 + 1/2 2 + 1/2 3 + ... + 1/2 h sumažina GP , kurio suma yra mažesnė nei 1 (kai h eina į begalybę, suma eina į 1). Tolesnėje analizėje atsižvelgiame į viršutinį sumos įvertinimą, kuris yra lygus 1.
Tai suteikia S = 2 h + 1 {1 + h / 2 h + 1 }
= 2H + 1 <strong> + H
~ 2 h + h
kaip h = log (n) , 2 h = n
Todėl S = n + log (n)
T (C) = O (n)

7
20 февр. Tanuj Yadav atsakymas, pateiktas vasario 20 d. 2017-02-20 23:14 '17, 11:14 pm 2017-02-20 23:14

Kurdami krūva, darysime prielaidą, kad jūs vykdote „iš apačios į viršų“.

  • Jūs patikrinate kiekvieną elementą ir palyginkite jį su savo vaikais, kad patikrintumėte, ar pora atitinka krūvos taisykles. Taigi lapai nemokamai patenka į krūvą. Taip yra todėl, kad jie neturi vaikų.
  • Pakilus, blogiausias atvejis, kai mazgas yra tiesiai virš lapų, bus 1 palyginimas (jie bus lyginami su didžiausia tik su viena vaikų karta).
  • Tęsdami savo artimiausius tėvus galima palyginti su dviem vaikų kartomis.
  • Tęsdami tą pačią kryptį, blogiausiu atveju turėsite lyginti šaknį (n). ir užsiregistruoti (n) -1 jų tiesioginiams vaikams, log (n) -2 jų tiesioginiams vaikams ir tt
  • Taigi, norėdami apibendrinti viską, atėjote į kažką panašaus į log (n) + {log (n) -1} * 2 + {log (n) -2} * 4 + ..... + 1 * 2 ^ {(logn) -1}, kuris yra nieko, išskyrus O (n).
5
03 июля '12 в 13:44 2012-07-03 13:44 Atsakymą pateikė Jones liepos 03 d. 12 val. 13:44 2012-07-03 13:44

Kuriant krūvą, mes pradedame nuo aukščio, logn -1 (kur logn yra n elementų medžio aukštis). Už kiekvieną elementą, esantį aukštyje "h", mes einame maksimaliu aukščiu iki (logn-h) žemyn.

  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) 
2
20 авг. Kartiko Goyal atsakymas 20 rug. 2015-08-20 12:26 '15 , 12:26 pm 2015-08-20 12:26

O (n) įrodymas

Šis įrodymas nėra fantastinis ir gana paprastas, tik įrodiau, kad visiškai dvejetainiam medžiui rezultatas gali būti apibendrintas visam dvejetainiam medžiui.

1
18 февр. Atsakymas pateikiamas Yi Y 18 vasario mėn. 2018-02-18 06:47 '18 at 6:47 2018-02-18 06:47

Sekvenciniai intarpai gali būti aprašyti taip:

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

Iki smuiko suderinimo n! =~ O(n^(n + O(1))) n! =~ O(n^(n + O(1))) , todėl T =~ O(nlog(n))

Tikimės, kad tai padės, optimalus būdas O(n) naudoja šio rinkinio krūvos algoritmą (užsakymas nesvarbu).

1
14 сент. Atsakymą pateikė Tomer Shalev 14 sep. 2013-09-14 13:45 '13, 13:45, 2013-09-14 13:45

@bcorso jau įrodė sudėtingumo analizės įrodymą. Tačiau tiems, kurie vis dar tiria analizės sudėtingumą, turiu tai pridurti:

Jūsų pradinės klaidos pagrindas yra susijęs su klaidingu teiginio reikšmės aiškinimu: „Įterpimas į krūvą priima O (log n) laiką“. Heap įdėjimas iš tiesų yra O (log n), bet jūs turite atpažinti, kad n yra krūvos dydis įterpimo metu .

Įterpiant n objektus į krūvą, i-ojo intarpo sudėtingumas yra O (log n_i), kur n_i yra krūvos dydis, kaip įterpiant i. Tik paskutinis įterpimas yra O (log n).

1
09 июля '17 в 4:28 2017-07-09 04:28 N.Vegetos atsakymas liepos 9 d. 17 d., 4:28 2017-07-09 04:28

Iš esmės, darbas atliekamas tik ant ne lapų mazgų statant krūvą ... ir atliktas darbas yra pakaitalo dydis, kad būtų patenkintas krūvos būklė ... kitaip tariant (blogiausiu atveju) suma yra proporcinga mazgo aukščiui ... visas užduoties sudėtingumas yra proporcingas aukščio dydžiui visi ne lapų mazgai, kurie yra (2 ^ h + 1 - 1) -h-1 = nh-1 = O (n)

0
31 мая '15 в 23:15 2015-05-31 23:15 Shubham Jindal atsakymas gegužės 31 d., 15 val. 23:15 2015-05-31 23:15

Tarkime, kad krūva yra N elementų. Tada jo aukštis bus Log (N)

Dabar norite įterpti kitą elementą, tada sudėtingumas bus toks: Žurnalas (N), turime palyginti visą kelią iki šaknies.

Dabar turite N + 1 elementus ir aukštį = žurnalą (N + 1)

Naudojant indukcijos metodą, galima įrodyti, kad injekcijos sudėtingumas būtų logiškas .

Dabar aš naudoju

log a + log b = log ab

Tai supaprastina: ∑logi = log (n!)

kuris iš tikrųjų yra O (nlogn)

Bet

čia darome kažką negerai, nes visais atvejais mes nepasiekiame viršaus. Todėl, atlikdami didžiąją laiko dalį, mes galime pastebėti, kad net nesiruošiame pusiaukelėje. Taigi, ši riba gali būti optimizuota, kad į kitą atsakymuose pateiktą matematiką matytumėte kitą griežtesnę ribą.

Šis supratimas atėjo man po detalių ir eksperimentų su krūvomis.

0
20 нояб. Atsakymas pateikiamas „ Fooo“ lapkričio 20 d 2018-11-20 08:36 '18 8:36 am 2018-11-20 08:36

"Linijinė krūvos ribinė laiko riba gali būti parodyta apskaičiuojant visų krūvų mazgų aukščių sumą, kuri yra maksimalus punktyrinių linijų skaičius. Puikus binarinis medis, kurio aukštis h, turintis N = 2 ^ (h + 1) - 1 mazgą, aukščių suma mazgai lygūs N - H - 1. Taigi, tai yra O (N). "

0
15 янв. atsakymas suteiktas sek3 sausio 15 d 2015-01-15 04:17 '15, 4:17 2015-01-15 04:17

Man labai patinka Jeremy paaiškinimas vakaruose ... čia yra kitas požiūris, kurį labai paprasta suprasti. http://courses.washington.edu/css343/zander/NotesProbs/heapcomplexity

kadangi pastatymas priklauso nuo panaudojimo, priklauso nuo to, ar yra krūvis, ir šlyties metodą, kuris priklauso nuo visų mazgų aukščių sumos. Taigi, norėdami rasti mazgų aukščio sumą, kurią suteikia formulė S = sumavimo iš π = 0 iki ı = h iš (2 ^ π * (hi)), kur h = logn yra medžio aukštis, sprendimas yra s, mes gauname s = 2 ^ (h + 1) - 1 - (h + 1), nes n = 2 ^ (h + 1) - 1 s = n - h - 1 = n-logn - 1 s = O (n), todėl konstrukcijos sudėtingumas yra O (n).

0
26 мая '14 в 12:19 2014-05-26 12:19 atsakymą pateikė Nitish Jain 26 gegužės 14 d. 12:19 2014-05-26 12:19

Другие вопросы по меткам или Задайте вопрос