Lekcja: "Algorytmy sortujące - drzewa binarne, sortowanie przez kopcowanie"
Schemat blokowy
Na podstawie przedstawionego algorytmu możemy ustalić klasę złożoności obliczeniowej rozbioru kopca.
Przeanalizujmy schemat blokowy rozbioru kopca. Pętla zewnętrzna nr 1 wykona się n -1 razy,a w każdym obiegu tej pętli pętla wewnętrzna wykona się maksymalnie log2n razy. Dlatego, gdy dokonamy górnego oszacowania otrzymamy klasę złożoności obliczeniowej rzędu O(n log n)w przypadku pesymistycznym.
Przypadek optymistyczny wystąpi tylko wtedy, gdy zbiór d[ ]będzie zbudowany z ciągu tych samych elementów. Dla tego przypadku klasa złożoności obliczeniowej będzie wynosić O(n).
