Heapsort: verschil tussen versies
Verwijderde inhoud Toegevoegde inhoud
k r2.7.1) (Robot: gewijzigd: zh:堆排序 |
→Efficiëntie: ruimtegebruik is O(1) |
||
Regel 177:
Heapsort is een vrij efficiënt algoritme, zowel qua ruimtegebruik als qua [[complexiteitsgraad|orde van looptijd]].
Heapsort is een "in-place" vervangingsalgoritme, wat wil zeggen dat het
De looptijd wordt bepaald door de aanroepen van MaakHeap en de doorlooptijd daarvan. De doorlooptijd van MaakHeap is lineair in de hoogte van de heap (de lengte van het langste pad van de wortel naar een blad). De heap is een binaire boom, dus de hoogte is van de boom is O(<sup>2</sup>log(N)), waarmee MaakHeap logaritmisch is in complexiteit. MaakHeap wordt in het hoofdalgoritme een keer aangeroepen voor ieder element van de invoerrij, waarmee de totale complexiteit uitkomt op O(N*<sup>2</sup>log(N)). Merk op dat het opbouwen van de initiële heap hier niets aan verandert. Ook hiervoor geldt dat de hoofdloop lineair is en de aanroepen van MaakHeap logaritmisch. Sterker nog, omdat er voor ieder hoogteniveau in de boom een maximaal aantal knopen is, kan zelfs vastgesteld worden dat de eerste opbouw van de heap lineaire tijd vergt en dus efficiënter is dan het hoofdalgoritme.
| |||