Zadanie 4 zaawansowane Heapsort

Rozważmy poniższy algorytm sortowania przez kopcowanie n-elementowej tablicy

A.

FixHeap(A; heapSize; i)

1 l <-2 * i

2 r<- 2 * i + 1

3 if l ≤ heapSize

4 then if l = heapSize

5 then largest<- l

6 else if A[l] > A[r]

7 then largest<- l

8 else largest<- r

9 if A[i] < A[largest]

10 then zamien A[i] z A[largest]

11 FixHeap(A; heapSize; largest)

ConstructHeap(A; r; n)

1 if r ≤

2 then ConstructHeap(A; 2 * r; n)

3 ConstructHeap(A; 2 * r + 1; n)

4 FixHeap(A; n; r)

HeapSort(A; n)

1 ConstructHeap(A; 1; n)

2 for heapSize n downto 2

3 do zamien A[1] z A[heapSize]

4 FixHeap(A; heapSize - 1; 1)

Określ złożoność obliczeniowa procedury HeapSort.

FixHeap

Czas działania procedury FixHeap na poddrzewie rozmiaru n zaczepionym w danym węźle i wynosi Θ(1) na poprawienie zależności między A[i], A[2*i] i A[2*i+1] plus czas potrzebny na rekurencyjne wywołanie FixHeap na poddrzewie zaczepionym w jednym z synów węzła i. Poddrzewa węzła mają każde rozmiar najwyżej 2n/3- najgorszy przypadek występuje, gdy ostatni rząd w drzewie wypełniony jest do połowy- czas działania FixHeap może zatem być opisany rekurencją

Z twierdzenia o rekurencji uniwersalnej mamy a=1,b=3/2, f(n)=Θ(1)

- co oznacza wystąpienie przypadku 2.

Stosując ten przypadek wyliczamy, że

ConstructHeap

Do obliczenia złożoności tej procedury wykorzystamy metodę iteracyjną. Ustalamy równanie rekurencyjne:

T(n)=2T(n/2)+lgn

=lgn+2T(n/2)

=lgn+2(lg(n/2)+2T)

=lgn+2lgn-2lg2+2²T(n/2²)

=lgn+2lgn-2lg2+2²))

=lgn+2lgn-2lg2+2²lgn-2²(2²)+2³T(n/2³)

…

=lgn+2lgn-2lg2+2²lgn-2²lg(2²)+…+2^klgn-2^klg(2^k)+2^k+1T(n/2^k+1)

=lgn(1+2+2²+..+2^k)-(2+2*2²+3*2³+…+k*2^k)

Tutaj założymy, że n=2^k więc k=lgn.

Weźmy s=2⁰+2¹+2²+…+2^k==2^k+1 -1

By uzyskać tą formułę, należy podjąć następujące kroki

s = 2⁰+2¹+2²+…+2^k

2s = 2¹+2²+…+2^k+2^k+1

s = -1+2^k+1

Stąd

Podobnie, weźmy

T=1*2¹+2*2²+3*2³+…+k*2^k

2T=1*2²+2*2³+…+(k-1)*2^k+ k*2^k+1

T= -2¹-2²-2³-…-2^k+k2^k+1

= k2^k+1-(2¹+2²+…+2^k)

= k2^k+1-(2^k+1-2)

=(k-1)2^k+1+2

Z tych założeń:

T(n)=lgn(2^k+1-1)-((k-1) 2^k+1+2)

=2nlgn-lgn-2nlgn+2n-2

=2n-lgn-2

=O(n)

Zatem złożoność procedury ConstructHeap wynosi O(n).

Złożoność procedury HeapSort wynosi O(nlgn), ponieważ wywołanie ConstructHeap zajmuje czas O(n), a każde z n-1 wywołań FixHeap zajmuje czas O(lgn).