Złożoność obliczeniowa algorytmu (prog/IT) IT: Złożoność obliczeniowa algorytmu (prog/IT) Witam, mam pytanie trochę dla programisty/informatyka Z góry przepraszam że pytam tutaj, lecz myślę że ktoś mi pomoże. Pseudokod: i = 1; wykonuj: j=1; dopóki(j>1) wykonuj: j=2; i=i+1; dopóki (i<2n+1) Z moich obliczeń: pętla i zaczyna sprawdzanie od 2<2n+1, jeżeli sprawdzenie zaczyna się od 1 to zwykłą pętla(1<n) sprawdzi się n razy, jeśli od 2 to n−1, to można wywnioskować że pętla sprawdzi się 2n razy? pętla wewnętrzna sprawdzi się raz bo jest fałszem, czyli przyjmie 1*2n Czy zatem: Lz = 2n Lw = 2n Lc = 4n O(n) ?

Pytający: Dopisz klamry, coby dało się ten pseudokod jednoznacznie zinterpretować. To są 2 pętle: wykonuj: {ciało} dopóki(warunek) czy co?

IT: i = 1; wykonuj: { j=1; dopóki(j>1) wykonuj: { j=2; } i=i+1; } dopóki (i<2n+1) Tak są dwie pętle, pierwsza do while, druga while, dziwnie to tak zapisujemy, ale wiesz początki studiów No i tu chodzi o złożoność czyli przy i=0 while się sprawdzi n+1 przy do while n

Pytający: Pętla wewnętrzna nigdy się nie wykona, bo tuż przed masz przypisanie j=1;. Warunek (j>1) oczywiście będzie jednokrotnie sprawdzany w każdym obiegu pętli zewnętrznej. Pętla zewnętrzna wykona się max{1,(2n+1)} razy (lub po prostu 2n+1 razy dla n≥0) i tyle samo razy będzie sprawdzony warunek (i<2n+1).

Pytający: Wróć, nie max{1,(2n+1)} razy, tylko max{1,2n} razy (i odpowiednio po prostu 2n razy dla n≥0).

IT : No właśnie przepraszam nie napisałem że n to bd duża liczba, ale to można się domyśleć Czyli zew 2n razy się sprawdzi, a że wew tylko raz bo Fałsz czyli przyjmie 2n. Razem 4n porównan. Dziękuję, chciałem się upewnić bo niedługo kolokwium