Strona 1 z 1
[Algorytmy] Oszacuj złożoność algorytmu
: 22 sty 2012, o 12:26
autor: bolek155
Czy ktoś pomógłby obliczyć złożoność algorytmu?
Kod: Zaznacz cały
i=0;
dopóki (i<n) wykonuj:
j=0
wykonuj:
j=j+1;
dopóki (j<n);
i=i+1;
[Algorytmy] Oszacuj złożoność algorytmu
: 22 sty 2012, o 12:52
autor: cyberciq
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
[Algorytmy] Oszacuj złożoność algorytmu
: 22 sty 2012, o 14:43
autor: bolek155
Polecenie jest takie: na podstawie fragmentu pseudokodu podaj liczbe porównań i oszacuj złożoność s sensie notacji O(~)
[Algorytmy] Oszacuj złożoność algorytmu
: 22 sty 2012, o 18:29
autor: adambak
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..