BRAK 7,13,20,21 nie mam do nich materiałów.

PYTANIE 1

Rozmiar danych - liczba pojedynczych danych wchodząca w jego skład.

Działanie dominujące - to taka że liczba wszystkich operacji elementarnych algorytmu jest proporcjonalna do liczby wszystkich operacji dominujących.

Złożoność pamięciowa algorytmu - niemalejąca funkcja, która pokazuje jak zmienia się liczba miejsc w pamięci niezbędna do wykonywania algorytmu w zależności od rozmiaru danych wejściowych.

Złożoność czasowa algorytmu - niemalejąca funkcja, która obrazuje jak zmienia się czas algorytmu od rozmiaru danych wejściowych.

Funkcje określające Złożoność obliczeniową algorytmu :

* n

* nlogn

* n do 2

* n do 2

* 2 do n

* n silnia

Złożoność obliczeniową algorytmu wyznaczamy aby określić czas działania i ilości zajmowanej pamięci.

PYTANIE 2

Złożoność pesymistyczna- ilość zasobów komputerowych potrzebnych przy najgorszych danych wejściowych rozmiaru n.

Złożoność średnia - ilość zasobów komputerowych potrzebnych przy typowych danych wejściowych rozmiaru n.

W(n) = a_mn^m+…+a_1n+a_0 = O(n^m) dla n>0.

A więc podstawiamy za n np.1 jest większe od zera wtedy możemy zauważyć że największą funkcją określającą ten algorytm jest mn^m bierzemy o-notacje z tego i wychodzi że O(n^m)

PYTANIE 3

O-notacja - służy do szacowania jednej funkcji przy pomocy innej. Funkcja f(n) jest co najwyżej funkcji g(n) jeśli istnieje

Własności:

1. f(n) , g(n) - dodatnie i rosnące funkcje

a>0, b

O(a* g(n)+b)=O(g(n))

Jeśli f(n)=O(a*g(n)+b) to f(a)=O(g(n))

2. Reguła dla Sum

Jeśli f(n)=O(S(n)) oraz g(n)=O(t(n)) to

F(n)+g(n)=O(max(S(n),t(n))

3. Reguła dla Iloczynu

Jeśli f(n)=O(S(n)) oraz g(n)=O(t(n)) to

F(n)*g(n)=O(S(n),t(n))

PYTANIE 4

Schemat Hornera

1 procedure wiel1;

2 begin

3 W := a[0];

4 for i := 1 to n do

5 p := x;

6 for j := 1 to i − 1 do

7 p := p _ x;

8 end for;

9 W := a[i] _ p +W;

10 end for;

11 end.

1. Algorytm wyznaczania wartości wielomianu metoda bezpośrednia

1 procedure wiel2;

2 begin

3 W := a[n];

4 for i := n − 1 downto 0 do

5 W := W _ x + a[i];

6 end for;

7 end.

1. Algorytm wyznaczania wartości wielomianu metoda Hornera

Dla wielomianu n-tego stopnia w zwykłej postaci należy wykonać n*(1+n)/2 mnożeń, a dla wielomianu po zastosowaniu schematu Hornera tylko n mnożeń! Różnica jest olbrzymia.

PYTANIE 5

Bez wartownika

Max := A[1];

i:=1;

While i<n do

i:=i+1;

if A[i]>Max then

Max:=A[i];

end if;

end while;

Złożoność T(n) = Tśr(n) = T
pes(n)= n-1 = O(n)

T(n)=n-1+1=2n-1=O(n)

Średnia liczba porównań znaki sterujące= n

Średnia liczba przypisań = lnn+0.577

Liczba porównań elementu(A[i]:=Max) n

Z wartownikiem

i:=1

while i<=n do

Max:=A[i]

A[n+1}:=Max;{ustawienie wartownika}

i:=i+1;

while n[i]<Max do

i:=i+1;

end while;

end while;

Złożoność T
śr(n) = T
pes(n)=n

Średnia liczba porównań znaki sterujące lnn+0.577+1

Średnia liczba przypisań lnn+0.577

Liczba porównań elementu(A[i]:=Max) n-1

PYTANIE 6

Max:= dowolny element zbioru S;

for dla pozostałych elementów X ze zbioru S do

if X>Max then

Max:=X;

End if;

End for;

Min:= dowolny element zbioru S;

for dla pozostałych elementów X ze zbioru S do

if X<Min then

Min:=X;

End if;

End for;

Złożoność T(n)= 2(n-1)=2n-2

2. Procedure MaxMin(s);

If

=2 then

If a>b then return(a,b)

Else return (b,a)

Else

Podzielić S na 2 równe podzbiory S
i S

(Max1,Min1)=MaxMin(S
);

(Max2,Min20= MaxMin(S
);

return

(MAX(Max1,Max2),MIN(Min1,Min2));

END IF;

Złożoność

T(n)= 1 gdy n=2

2T(
)+2 gdy n>1

T(2
)=
n-2 = O(n)

PYTANIE 8

Sortowanie przez wybór

 

Algorytm polega na wyborze elementu minimalnego i wstawieniu go na początek:

 

for i:=1 to n-1 do

begin

   { wybierz element minimalny z fragmentu tablicy A[i..n]  }

   { zamień wybrany element z elementem i-tym                  }

end;

 

Kompletna procedura może być zapisana w formie:

 

procedure Selection_sort;

var i, j, min: integer;

     tmp: elem_type;

begin

   for i := 1 to n-1 do

   begin

      min:=i;

      for j:=i+1 to n do

         if A[j] < A[min] then min:=j;

      tmp:=A[i];   A[i]:=A[min];   A[min]:=tmp;

   end;

end;

 

Złożoność pamięciowa O(1) - algorytm sortuje w miejscu, wymaga bowiem jedynie kilku zmiennych prostych (i, j, min;  tmp).

 

Złożoność czasowa

- ilość porównań:

           

- ilość przestawień

           

Własności:

      stabilny

      liniowa ilość przestawień (optymalny)

      stała ilość porównań (kwadratowa i nie zależy początkowego posortowania danych)

      prosty i szybki dla małych n

 

Połowkowy

for i := 2 to n1 do

x:= A[i] ; l:=1; p:=i-1;

while l
p do

m:=(l+p)div2;

if x.klucz<A[m].klucz then

p:=m-1

else l:=m+1;end if;

end while;

for j:=i-1 downto l do

A[j+1]:= A[j];end for;

A[l]:=x;

End for;

Złożoność

Pmax(i)=

Ppes(n) =
=
=n(log n - c)+c=O(nlogn)

PYTANIE 9

Kopcem nazywamy etykietowane, doskonałe drzewo binarne częściowo uporządkowane.

Etykietowane drzewo binarne D = <V, E, et> jest kopcem wtedy i tylko wtedy, gdy

(1) D jest drzewem częściowo uporządkowanym:
et(v) < et(v.lewy) i et(v)< et(v.prawy)
dla wszystkich wierzchołków v ∈V,

(2) D jest drzewem doskonałym:
wszystkie poziomy drzewa, z wyjątkiem co najwyżej ostatniego poziomu, są maksymalnie zapełnione, a na ostatnim poziomie wszystkie liście są zgrupowane maksymalnie na lewo.

Własności:

1. Etykiety na dowolnej drodze od korzenia do liścia tworzą ciąg uporządkowany rosnąco.

2. Element najmniejszy wśród etykiet wierzchołków znajduje się w korzeniu drzewa.

Dla każdego węzła na poziomie i (liczonym od dołu) maksymalna ilość porównań i przestawień przy poprawianiu w dół jest równa i, zaś ilość węzłów na tym poziomie n/2ⁱ. Pesymistyczna złożoność budowania kopca jest zatem:

)

procedure create_heap_2;

var i: integer;

begin

   hl:=n;

   for i:=n div 2 downto 1 do down_heap(i,hl);

end;

lub:

1 procedure kopiec w dół(A, i);

2 begin

3 l := 2 _ i;

4 r := 2 _ i + 1;

5 if l ¬ heap size(A) and A[l] > A[i] then

6 largest := l;

7 else

8 largest := i;

9 end if;

10 if r ¬ heap size(A) and A[r] > A[largest] then

11 largest := r;

12 end if;

13 if largest 6= i then

14 zamiana(A[i],A[largest]);

15 kopiec w dół(A, largest);

16 end if;

17 end.

1. Algorytm przesuwania elementu w dół kopca

1 procedure kopiec w góre(A, x);

2 begin

3 heap size(A) := heap size(A) + 1;

4 i := heap size(A);

5 while i > 1 and A[i div 2] < x do

6 A[i] := A[i div 2];

7 i := i div 2;

8 end while;

9 A[i] := x;

10 end.

1. Algorytm przesuwania elementu w góre kopca

PYTANIE 10

Kolejka

Kolejka jest strukturą liniowo uporządkowanych danych w której dołączać nowe dane można jedynie na koniec kolejki a usuwać z początku. Procedura usunięcia danych z końca kolejki jest taka sama, jak w przypadku stosu, z tą różnicą, że usuwamy dane od początku a nie od końca.
Pierwszy element (a dokładniej wskaźnik do jego miejsca w pamięci) musi zostać zapamiętany, by możliwe było usuwanie pierwszego elementu w czasie stałym O(1). Gdybyśmy tego nie zrobili, aby dotrzeć do pierwszego elementu należałoby przejść wszystkie od elementu aktualnego (czyli ostatniego), co wymaga czasu O(n).
Działanie na kolejce jest intuicyjnie jasne, gdy skojarzymy ją z kolejką ludzi np. w sklepie. Każdy nowy klient staje na jej końcu, obsługa odbywa się jedynie na początku.
Schemat kolejki wygląda następująco:

PYTANIE 17

For i:=2 to n do

x:=a[i]; A[0]:=x; {ustawienie wartownika}

j:=i-1;

while x.klucz<A[j].klucz do

A[j+1]:=A[j]; j:=j-1;

End while;

A[j=1]:=x;

End for;

Tpes(n)=

=2+3#...+(n-1+1)=
(n-1)=
(n
+n)-1=O(n
)

Tsr(n)=
=

=O(
)

PYTANIE 16

For i:=1 to n-1 do

K := i; x:=A[i];

For j:=i+1 to n do

If A[j].klucz< x.klucz then

K :=j; x:=A[j];

End If;

End for;

A[k]:= A[i];

A[i]:= x;

End for;

Tsr(n) = Tpes(n) =
=
(n-1) =
= O(
)

PYTANIE 18

Sortowanie szybkie (quick sort)

 

Algorytm sortowania szybkiego zaprojektowany został na podstawie zasady `dziel i zwyciężaj'. Polega zatem na rozbiciu zadania na dwa mniejsze, wykonaniu sortowania niezależnie dla obu części i połączenia wyniku. Ogólny schemat algorytmu można zapisać następująco:

 

Quick_sort(S);

 

if S =1 then return(S) else

begin

     wybierz dowolny element vS;

     podziel S na S₁ i S₂ takie, że wS₁ wv  wS₂ w>v;

     Quick_sort(S₁); Quick_sort(S₂);

     połącz S₁ i S₂;

end;

 

Proces podziału polega na:

      przeglądaniu ciągu od lewej i wyszukiwaniu elementów większych od v,

      przeglądaniu ciągu od prawej i wyszukiwaniu elementów mniejszych od v,

      zamianie znalezionych elementów.

aż do rozdziału ciągu na dwa podciągi. Wybór elementu v jako pierwszego elementu ciągu i wstawienie go w miejsce zejścia się obu procesów przeglądania pozwala na rozdział ciągu w tej samej strukturze danych (tablicy) i sortowanie niezależne obu fragmentów w tej samej tablicy. Zapewnia to, że proces łączenia nie wymaga żadnych operacji.

Kompletna procedura może być zapisana następująco:

 

procedure Quick_sort(l, r: integer);

var  i, j: integer;

     v, tmp: elem_type;

begin

   v:=A[l];   i:=l;   j:=r+1;

   repeat

      repeat i:=i+1 until A[i]>=v;

      repeat j:=j-1 until A[j]<=v;

      if i<j then

      begin   tmp:=A[i];  A[i]:=A[j];  A[j]:=tmp;

      end;

   until i>=j;

   A[l]:=A[j];   A[j]:=v;

   if j-1>l then Quick_sort(l,j-1);

   if j+1<r then Quick_sort(j+1,r);

end;

 

Wybór pierwszego elementu tablicy jako elementu podziału powoduje dodatkowo konieczność wstawienia wartownika na końcu tablicy, aby zapewnić zakończenie pierwszej pętli wewnętrznej, gdy element v jest największy w tablicy.

Złożoność czasowa algorytmu.

 - złożoność pesymistyczna:

 

           

 - złożoność oczekiwana:

 

           

Ponieważ podział ciągu jest jednakowo prawdopodobny w każdym miejscu tablicy, zatem

           

Stąd

           

Ponieważ

           

Zatem

           

 

Sortowanie szybkie sortuje zatem w czasie średnim O(nlog(n)).

 

Własności:

      algorytm niestabilny

      złożoność pamięciowa ze względu na rekurencję w przypadku pesymistycznym O(n).

      testy wykazują najlepszą efektywność tej metody sortowania

Wybór elementu może być przyczyną poprawienia efektywności w pewnych przypadkach, np.

      wybór pierwszego elementu daje złożoność O(n²) dla ciągu uporządkowanego.

      wybór losowy wydaje się bardziej korzystny, lecz wymaga przeprogramowania (wartownik z oby stron)

      wybór mediany z dowolnych trzech elementów (np. pierwszy, ostatni i środkowy) zapewnia, że zawsze będzie podział na dwie części, z których krótsza będzie miała co najmniej jeden element.

PYTANIE 19

W informatyce grafem nazywamy strukturę G=(V, E) składającą się z węzłów (wierzchołków, oznaczanych przez V) wzajemnie połącznonych za pomocą krawędzi (oznacznych przez E).
Grafy dzielimy na grafy skierowane i nieskierowane

niekierowany graf
skierowany graf

Rysunek 1 rysunek 2

Omówmy najpierw macierz sąsiedztwa.
Budujemy tablicę o rozmiarach V*V, gdzie V-liczba wierzchołków. Następnie wypełniamy ją zerami- jeśli dwa wierzchołki nie są połączone krawędzią i jedynkami- jeśli dwa wierzchołki są połączone.

Złożoność pamięciowa O(V
)

Lista incydencji.
Należy utworzyć listę dla każdego wierzchołka v, w której przechowujemy zbiór wierzchołków połączonych krawędzią z v. Lista dla grafu z rysunku 1 wygląda następująco:

1: 2, 3, 5 4: 2, 3, 5
2: 1, 3, 4

3: 1, 2, 4 5: 4, 1   

Złożoność pamięciowa O(V+E)

Lista krawędzi jest to lista, na której przechowujemy wszystkie krawędzie występujące w grafie.
Przykład dla grafu skierowanego z rys.2:

1 - 2 3 - 2

2 - 4 4 - 3

2 - 5 5 - 1

3 - 1 5 - 4

Złożoność pamięciowa O(E)

Macierz incydencji to tablica o rozmiarach V*E. Składa się ona z E kolumn i V wierszy, jeśli krawędź wychodzi z danego wierzchołka to piszemy w odpowiedniej kolumnie (-1), jeśli do niego wchodzi piszemy (+1), jeśli wierzchołek nie należy do krawędzi piszemy 0, jeśli jest to pętla własna piszemy 2.

Złożoność pamięciowa O(E*V)

PYTANIE 23

Algorytm Kruskala

VS- rodzina rozłącznych zbiorów wierzchołków. Każde V
Vs reprezentuje pewne drzewo rozpinające należącego do lasu rozpinającego.

1.Rozpatrujemy krawędzie w kolejności kosztu

2.Niech (v,w) to kolejna rozpatrująca krawędź

a) (v,w) należą do tego samego zbioru Vs to krawędź tą pomijamy

b) (v,w) należą do dwóch różnych zbiorów Vs(w1,w2) to krawędź wędruje do drzewa i scalamy zbiory w1 i w2

ALGORYTM

Vs<=0; T<=0;

Skonstruuj kolejkę priorytetową Q zawierającą wszystkie krawędzie zbioru S.

For dla każdego v
V do

Dodaj {V} do Vs

End for;

While (Vs)>1 do

Wybierz z kolejki Q krawędź Vw o najmniejszym koszcie

Usuń Vw ze zbioru Q

If v,w należą do różnych zbiorów w1 i w2 w Vs then

Zastąp w1 i w2 i dodaj (v,w) do T

End If;

End while;

Złożoność

1.O(e)

2.Inicializacja O(n)

3.while

a) O(loge)

b) FIND I UNION O(elog*e)

Czyli

Tsr = O(elog e)

T(n) = O(n
logn)

PYTANIE 25

Dodawanie reszty

25zł,10zł.5zł,1zł

63zł-reszty

Wydajemy resztę w ten sposób:

2*25, 1 *10, 3*1

2+1+3=6

A)wybrać monetę , której wartość nie przekracza 63zł, to jest 25zł.

B)wstawić monetę na listę i odjąć jej wartość od 63zł - otrzymujemy 38zł

C)powtórzyć kroki A i C dla reszty równej 38,13 i3 zł.

Zadanie pakowania plecaka

W-ciężar maksymalny plecaka

A = {a
,a
, … ,a
}

{ w
,w
, … ,w
}- waga

{ p
,p
, … ,p
}- zyski dane

Wybieramy taki produkt żeby całkowity ciężar obiektów
w oraz całkowity zysk był jak największy.

Formalnie 2n+1

{ w
,w
, … ,w
}

W

{ p
,p
, … ,p
}

Q=

Przy ograniczeniach

1. z
   = (0,1) dla
   i

2. 
   

Kolorowanie grafu

1 procedure graf kolorowanie zachłanne (G : graf; nowy kolor : zbiór);

2 var jest : boolean;

kolor : integer;

v,w : integer;

3 begin

4 kolor := 0;

5 while istnieja niepokolorowane wierzhołki w G do

6 nowy kolor := ;;

7 kolor := kolor + 1;

8 v := pierwszy niepokolorowany wierzchołek w G;

9 while v <> null do

10 jest := false;

11 w := pierwszy wierzchołek w zbiorze nowy kolor;

12 while w <> null do

13 if istnieje krawedz pomiedzy v i w w G then

14 jest := true;

15 end if;

16 w := nastepny wierzchołek w zbiorze nowy kolor;

17 end while;

18 if not jest then

19 oznacz v jako pokolorowany kolorem kolor;

20 dołacz v do zbioru nowy kolor;

21 end if;

22 v := nastepny niepokolorowany wierzchołek w G;

23 end while;

24 end while;

25 end.

1. Kolorowanie grafu algorytmem zachłannym

Polega na przyporządkowaniu każdemu wierzchołkowi koloru tak aby:

• Każde 2 wierzchołki połączone krawędzią miały różne koloru

• Liczba kolorów była minimalna

Graf jest k - kolorowalny jeśli istnieje przyporządkowanie wierzchołkom G liczb całkowitych nazywanych kolorami w ten sposób że żadne 2 sąsiednie wierzchołki nie mają tego samego koloru.

PYTANIE 26

Sformułowanie problemu komiwojażera
Zbudujmy graf ważony, którego wierzchołki są miastami. Każda parę miast połączmy krawędziami. Każdej krawędzi nadajemy wagę równa 'odległości' miedzy miastami odpowiadającymi wierzchołkom, które są końcami tej krawędzi. Otrzymujemy w ten sposób graf pełny, który ma tyle wierzchołków ile miast musi odwiedzić komiwojażer (wliczając w to miasto, z którego wyrusza). Odwiedzenie wszystkich miast odpowiada cyklowi, który przechodzi przez każdy wierzchołek danego grafu dokładnie raz. Cykl taki nazywamy cyklem Hamiltona. Poszukujemy wiec w grafie pełnym cyklu Hamiltona o minimalnej sumie wag krawędzi.

a)

min:=

for i:=1 to (n-1) do

p:= i-ta permutacja wierzchołków
,
, …,

Niech d(p) jest drogą w grafie odpowiadającym permutacji p jego wierzchołków

If koszt (d(p))<min then

Droga:= d(p);

Min:= koszt(d(p));

End If;

End for;

Złożoność tego algorytmu to n silnia/2.

b)

1. Rozpatrzmy wszystkie krawędzie grafu w kolejności wzrostu ich kosztów.

2. Włączyć krawędzie do poszukiwanej drogi wtedy gdy spełnione są warunki:

• Włączenie krawędzi nie powoduje że któryś z wierzchołków drogi ma stopień większy niż 2

• Włączenie krawędzi nie powoduje powstania cyklu chyba że liczba krawędzi dogi równa jest liczbie wierzchołków grafu

Złożoność tego algorytmu O(n
)

PYTANIE 27

Cykl Eulera

Do powstania cyklu Eulera przyczynił się tzw. problem mostów królewieckich. Przez Królewiec (dziś Kaliningrad) przepływała rzeka, w rozwidleniu której znajdowały się 2 wyspy. Na rzece znajdowało się 7 mostów (patrz rys.). Miejscowa ludność co rok urządzała zabawę, która polegała na próbowaniu przebycia wszysktkich mostów dokładnie raz. Problemem tym zajął się Leonhard Euler, szwajcarski matematyk, fizyk i astronom. Udowodnił on, że nie jest to możliwe, powodem tego jest nieparzysta liczba wejść na mosty na wyspach oraz po obu stronach rzeki.

Cyklem Eulera w grafie nazywamy cykl (drogę, która zaczyna się i kończy w tym samym wierzchołku), który zawiera każdą krawędź dokładnie raz.

Warunek istnienia cyklu Eulera: po pierwsze graf musi być spójny (musi istnieć droga łącząca każdą parę wierzchołków). Jeżeli graf jest spójny i skierowany to do każdego wierzchołka musi wchodzić i wychodzić tyle samo krawędzi. Jeżeli graf jest spójny i nieskierowany to liczba wychodzących krawędzi z każdego wierzchołka musi być parzysta.

Warunek istnienia drogi Eulera :istnieje wtedy i tylko wtedy gdy graf jest spójny i zawiera co najwyżej 2 wierzchołki stopnia nieparzystego.

Cykl Hamiltona

Jest to droga Hamiltona zamknięta.

O(k
)

PYTANIE 15

WG. Wzoru

Function w
p(n,m:integer):integer

Begin

If (n=m) or (m=0) then

Wsp:=1;

Else

Wsp:=wsp(n-1,m)+wsp(n-1,m-1);

End if;

End;

T(n)=1+2+4+...+2
=
=2
-1=O(2
)

LUB

For j:=0 to n do {inicjalizacja}

Pom[j]:=1;

End for;

For i:=2 to n do {kolejne fazy}

{Pom[j]=(
) dla 0
j
i-1}

For j:=j-1 downto 1 do

Pom[j]:=Pom[j-1]+Pom[j];

End for;

{Pom[j]=(
) dla 0
j
i}

End for;

{Pom[j]=(
) dla 0
j
n}

T(n)=n+1+
=n+1+
=2+
=O(n
)

PYTANIE 12

Sortowanie to jest ulepszoną wersją sortowania przez wybór (selection sort), w którym wybieranie elementu minimalnego (maksymalnego) odbywa się bardziej efektywnie przy użyciu kopca. Kopiec (zupełny) ma strukturę drzewa binarnego o następujących własnościach:

      wartość następnika jest nie większa od wartości poprzednika (własność kopca).

      elementy zapełniają drzewo binarne poziomami od lewej do prawej (własność zupełności).

Z faktów tych wynikają następujące własności:

      element maksymalny jest w korzeniu kopca.

      liście drzewa umieszczone są na ostatnim i (być może) przedostatnim poziomie

      na dowolnej ścieżce wgłąb drzewa elementy są uporządkowane.

Algorytm sortowania można sprowadzić do następujących operacji:

 

utwórz kopiec z elementów ciągu;

while kopiec niepusty do

begin

     wstaw element maksymalny na koniec ciągu;

     skróć ciąg do posortowania;

     delete_max;

End;

 

Ponieważ sortowane są elementy tablicy najkorzystniej jest zaimplementować kopiec w tej samej tablicy. Implementacja taka jest łatwa przy następujących założeniach:

      n elementów kopca zajmuje n pierwszych elementów tablicy A[1..n]

      korzeniem kopca jest element A[1]

      potomkami elementu A[i] są elementy A[2*i] i A[2*i+1]

Cała procedura sortowania może być zapisana w postaci:

 

begin

   create_heap_1; 

   for i:=n downto 1 do

   begin

      v:=delete_max(hl);      A[i]:=v;

   end;

end;

Złożoność poszczególnych operacji na kopcu wynika ze jego struktury. Na całkowicie zapełnionym k-tym poziomie kopca znajduje się 2^k-1 elementów, zatem kopiec o wysokości h zawiera co najmniej:  2⁰ + 2¹ + 2² + ...+ 2^h-2 + 1 = 2^h-1 elementów, zaś najwięcej 2^h - 1 elementów. Zatem

                        2^h-1   n   2^h-1

                               h-1  log(n) < h

Stąd h=(log(n)).

wykonanie n-krotne na skracającym się kopcu wymaga:

)

Pesymizm

PYTANIE 11

1 procedure kopiec buduj(A, n);

2 begin

3 heap size(A) := n;

4 for i := n div 2 downto 1 do

5 kopiec w dół(A, i);

6 end for;

7 end.

1. Algorytm budowania kopca

PESYMISTYCZNE O(n)

---