PDA

Zobacz pełną wersję : Obliczanie złożoności obliczeniowej kodu w C++



biniu321
30-01-09, 11:52
Witam!
Mam do rozwiązania taki przypadek: Jest to ciąg Fibonacciego i mam obliczyć złożoność tego kodu Czy ktoś umiałby obliczyć jego złożoność obliczeniową O (duże O)? Z góry dzięki za odpowiedź! Pozdrawiam!

int Fib(int n)
{
int k, f0, f1, f2;
k = 0; f0 = 1; f1 = 1;

while (k != n)
{
k = k + 1;
f2 = f0 + f1;
f0 = f1;
f1 = f2;
};
return f0;
};

bctb107
06-01-11, 06:36
Liczba całkowita liczba operacji podstawowych, tych, które mają stały okres czasu. To wszystko na ten temat.

Na przykład, kod int suma = 0; jest 1 podstawowych operacji. Następnie j = 0; jest kolejnym podstawowych operacji. Następnie j <i form kolejny podstawowych operacji. Liczba tych, i masz złożoności czasowej.

Na przykład, weźmy pętli


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

W tej pętli skończyć się oceny j = 0, gdy j <całości Ia i + 1 razy, j + + i czasy, i Sum + +; i razy. Tak więc całkowita liczba operacji podstawowych jest: 1 + (i + 1) + i + i = 3i + 2.

Następnie podejmuje blok kodu,


int Sum = 0;
int j;
for (j = 0; j < i; j++)
Sum++;
cout << Sum << endl;
i--;

Tutaj mamy int suma = 0; w jednej operacji, for (j = 0; j <i, j + +) Sum + +; biorąc 3i + 2 operacji cout <<suma <<endl; przy 1 pracy (lub 2 operacje, w zależności jak na to spojrzeć, ale całość ma stałej ilości czasu i tak). Wtedy ja -; ma jednej operacji. Więc to w sumie 1 + (3i + 2) + 1 + 1 = 3i + 5.

Następnie podejmuje blok kodu,



int i = N;
while (i > 0)
{
we calculated this to take 3i + 5 operations
}


Za każdym razem, pętli, 1 + (3i + 5) operacje są wykonywane (jeden jest dodawany do porównania i> 0).