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.
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”.