Złożoność obliczeniowa - wyznaczanie wzorów na liczbę porównań

Question

Cześć! 

Chciałbym poprosić was o pomoc, ponieważ od pewnego czasu na studiach męczy mnie pewne zagadnienie, z którym nie mogę sobie poradzić. Postaram się mój problem wytłumaczyć jak najlepiej, ale nie gwarantuję, że gdzieś po drodze się nie pomylę.

A więc tak: mam na studiach przedmiot, który nazywa się "Podstawy informatyki" i właściwie wszystko było w porządku, dopóki nie pojawił się temat o nazwie "Złożoność obliczeniowa algorytmów". Niestety, ze względu na niewystarczającą ilość czasu to zagadnienie nie zostało dokładnie wytłumaczone i przez to pojawił się problem. Bo o ile samą definicję złożoności powiedzmy, że rozumiem, tak nigdy nie mogę prawidłowo wykonać zadania o takiej treści:

Na podstawie fragmentu pseudokodu podaj liczbę porównań i oszacuj złożoność w sensie notacji O(·).

A tu przykładowa treść zadania:

i=0;
while(i<2*n)
{
  j=1;
  do
  {
    j=j*3;
  }while(j<4*n);
 i=i+1;
} 

Jeżeli w tym zadaniu chodziłoby TYLKO o wyznaczenie złożoności algorytmu, to jeszcze jest to przeze mnie do zrobienia. Ale niestety, oprócz tego muszę jeszcze wyznaczyć wzór na ilość porównań pętli zewnętrznej (Lz) i pętli wewnętrznej (Lw), a następnie wszystko zsumować (Lc). Takie uwarunkowanie mam podane w zadaniu:

L jest liczbą porównań, a jako rozwiązanie zadania podajemy Lw, Lz, Lc, O(·)

I powiem szczerze: nigdy nie potrafiłem wyznaczyć prawidłowych wzorów. Za każdym razem podaję odpowiedź po części dobrą (bo złożoność, co najciekawsze, zawsze podaję prawidłową), ale zadanie nie zostanie uznane, dopóki nie będzie zrobione w całości. I tu zwracam się do was o pomoc: czy mógłby mi ktoś wyjaśnić, na jakiej podstawie wyznacza się te wzory na ilość porównań? Ja wiem, że to pewnie nie jest trudne, ale naprawdę nie mogę sobie z tym poradzić. Byłbym bardzo wdzięczny za jakiekolwiek wyjaśnienie, które pozwoli mi to zrozumieć.

A, i jeśli jest to istotne, to muszę to policzyć na kartce, bez użycia komputera i kalkulatora.

Answer 1

do porównania dochodzi 2 razy: 

while(i<2*n)

i tu:

}while(j<4*n);

pętla (nazwijmy ją i by nie pisać zewnętrzna i wew. ) i wykonuje się zawsze 2n razy. Ale wykona 2n+1 porównań (dlatego że (dla przykładu n = 10) na początku masz i = 0 potem 1,2,3 i tak aż i = 20 co warunku już nie spełnia.
Pętla wykona się 20 razy bo 20 razy warunek był spełniony ale porówna 21 bo warunek nie był spełniony dla 20 (20 nie jest większe od 20) więc pętla i wykona zawsze 2n porównań

z pętlą j (wew) jest więcej problemów: po pierwsze do..while sprawdza warunek na końcu pętli. więc gdy j = 1 nie sprawdza warunku. 
Znów z przykładem n = 10: dla n = 10 warunek pętli wygląda tak: j < 40 więc pętla będzie się wykonywać aż j nie osiągnie wartości większej od czterdziestu  + 1. w kolejnych iteracjach pętli, zmienna j przyjmuje wartości kolejnych potęg 3. 
j = 3, j = 9, j = 27, j = 81 ...
a więc dla n = 10:
3 < 40
9 < 40
27 < 40
81 < 40 FAŁSZ! 
więc dla n = 10 pętla wykonała się 4 razy. warunek można zapisać ładniej tak:
3^x < 4n (x ilość iterancji)
szukamy miejsca gdzie warunek "zmieni" stan (czyli miejsce zerowe):
3^x - 4n = 0 ; obliczamy względem x 
x = log3(4n)
zaokrąglając w góre:
x = ceil(log3(4n))
a więc teraz podstawiając pod n jakąś liczbę otrzymasz ilość iteracji która się wykona.

Mam nadzieje że mając te dane wiesz jak policzyć sumaryczną ilość porównań? 

Nie dam sobie ręki uciąć że wszystkie te obliczenia są poprawne!  na 98% tak ale lepiej niech mnie ktoś jeszcze sprawdzi.   

Comments

Dobra, chyba zaczynam coś ogarniać, bo robię już sam obliczenia i wydaje mi się, że wychodzi mi dobrze. A twoje obliczenia też są prawidłowe, bo w piątek prowadzący pokazywał nam rozwiązanie i wyszło tak samo, jak tobie.

Czyli jest w porządku, powinienem już sobie dalej poradzić, ale poćwiczę to jeszcze, bo muszę być dobrze przygotowany do kolosa. Dziękuję bardzo za pomoc, w końcu ktoś mi wytłumaczył, jak to się powinno robić krok po kroku. Jeszcze raz, wielkie dzięki!