Liczenie złożoności obliczeniowej


(Andrzej Spider) #1

Czy mógłby mi ktoś pokazać jak liczy się złożoność obliczeniową algorytmu, np takie zadanie:

Proszę obliczyć złożoność obliczeniową następującego fragmentu programu:


for (int i = 0; i < n; ++i)

   for(int j = 0; j < i +i; ++j)

          sum = sum + 1;

lub takie

int fun(int n)

{

 if(n==0) return1;

 return fun(n – 1) + fun(n – 1);

}

To nie jest żadna praca domowa, chce żeby tylko mi ktoś wytłumaczył jak to się liczy. Nawet nie wiem czy wynik to liczba, jakaś zmienna czy co.


(Jam1234) #2

http://ksiegarnia.pwn.pl/produkt/2790/m ... retna.html

Najczęściej próbujesz policzyć "czas wykonania" w zależności od rozmiaru danych: f(n) = ?

Ogólnie zakładamy, że pewne operacje zajmują czas stały (niezależny od n). W tym przypadku będzie to obliczenie sum = sum + 1 lub wykonanie kroku pętli for.

Pierwszy for wykona się n razy. Wobec tego drugi wykona się:

0 + 2 + 4 + ... + 2n = 2 * (1 + 2 + 3 + ... + n) = 2 * n * (n + 1) / 2 = n^2 + n

A zatem (uprośćmy to) obliczenie sum = sum + 1 wykona się n^2 + n razy (n^2 - n do kwadratu).

A teraz robi się taką "sztuczkę", że próbujesz oszacować klasę funkcji notacją O. http://pl.wikipedia.org/wiki/Asymptotyc ... po_wzrostu

W tym przypadku będzie to O(n^2), bo "dla dużych n, + n staje się nieistotne".