[Algorytmy] Oszacuj złożoność algorytmu

bolek155 · Post autor: **bolek155** » 22 sty 2012, o 12:26

Czy ktoś pomógłby obliczyć złożoność algorytmu?

i=0;
dopóki (i<n) wykonuj:
j=0
wykonuj:
j=j+1;
dopóki (j<n);
i=i+1;

cyberciq · Post autor: **cyberciq** » 22 sty 2012, o 12:52

Napisz, na czym konkretnie polega problem, bo w sieci jest dużo przykładów obliczania złożonosci algorytmów, które ładnie pokazuja jak to się robi. Najpierw ustal operację dominującą. A potem liczymy ile wykonań tej operacji będzie.

pozdrawiam

bolek155 · Post autor: **bolek155** » 22 sty 2012, o 14:43

Polecenie jest takie: na podstawie fragmentu pseudokodu podaj liczbe porównań i oszacuj złożoność s sensie notacji O(~)

adambak · Post autor: **adambak** » 22 sty 2012, o 18:29

zauważ, że na każde wykonanie kroku pętli zewnętrznej wypada \(\displaystyle{ n}\) kroków w pętli wewnętrznej, stąd złożoność to \(\displaystyle{ O(n^2)}\).. oczywiście możesz policzyć to dokładnie ile będzie kroków, bo będzie nieco mniej (zważywszy na inną strukturę obu pętli tzn do..while i while..do), ale zrozumiałem że chodzi tylko o to..