Witam, mam pytanie odnośnie obliczania złożoności czasowej INSERTION-SORT(A).
W Cormenie początek algorytmu wygląda tak:
koszt liczba wykonań
for j<-2 to lemgth[A] c1 n
do key<-A[j] c2 n-1
Czy ktoś może powiedzieć mi, czemu liczba wykonać pierwszej linijki jest o jeden większa od liczby wykonań drugiej? Chodzi o to, że pierwsza wykona się zawsze nawet jak nie zostanie spełniony warunek i dlatego o jeden "n" więcej?
Odpowiem Ci cytując:
"Kiedy pętla for lub while kończy się w zwykły sposób (tzn. przez sprawdzenie warunku w nagłówku pętli), sprawdzenie wykonywane jest o jeden raz więcej niż treść pętli".
Rozumiem, że dotyczy to tylko while i for? Dla np. repeat until już liczymy normalnie?
W pętli for i while masz tak:
1: while / for
2: doSomething
zatem wchodzisz do while (1 raz) i jeśli spełniony to robisz doSomething (1raz), potem sprawdzasz warunek (2 raz) i jeśli spełniony to wykonujesz to co jest w pętli (2 raz). Po kolejnych iteracjach wchodzisz do pętli (n-ty raz) i po wykonaniu sprawdzasz warunek (n+1 raz) który już nie będzie spełniony ale żeby się o tym przekonać musiałeś go sprawdzić. Po takim wykonaniu masz n+1 dla 1 punktu i n dla drugiego.
Jeśli chodzi o do while
1: doSomething
2: while
Tutaj najpierw coś robisz (1 raz), potem sprawdzasz warunek (1 raz) i jeśli spełniony to wracasz do początku. Wtedy zawartość pętli (2 raz) i sprawdzenie warunku (2 raz) aż dochodzisz do sytuacji, że wykonałeś zawartość n razy i sprawdzasz n-ty raz warunek - nie jest on spełniony więc przechodzisz dalej. Podsumowując obie części (1 i 2) wykonałeś n razy.
Bardzo dobrze wytłumaczone, dziękuję.
Zatem przy długości tablicy równej 3
1: while / for // to wykona się 4 razy ??
2: doSomething
Dobra, w sumie to zależy też od warunku, więc głupie pytanie. Załóżmy, że mamy tam:
for j<-1 to 3
Tak jak wspomniałem wykona się 4 razy?
A czy pesymistyczny czas wykonania while wynosi tyle co suma szeregu arytmetycznego?
Mam tutaj na myśli sprawdzanie warunków.
A w zasadzie chodzi mi o to, ile razy w najgorszym przypadku wykona się sprawdzenie warunków w while. Nie jestem pewien, czy jest to (n^2+n)/2?