Ciąg Fibonacciego

0

Witam

  1. Jak mam uzasadnić poprawność algorytmu dla ciągu Fibonacciego w wersji iteracyjnej??
  2. Czy na podstawie pseudokodu mogę ustalić złożoność czasową i pamięciową? Jeśli tak to proszę o podanie jakiegoś bardzo trywailnego sortowania dla przykładu.

Pozdrawiam

Ad 1

[code]int fib_iter(int n)
{int f[0..n];
if (n>0)
f[0]=1;
f[1]=1;
for (int i=2;i<=n;i++)
f[i]=f[i-1]+f[i-2]
[/code]

Pętla for wykona się n-1 razy i podczas jej iteracji następuje jedno przypisanie wartości zmiennej i, zatem jego złożoność to O(n)? Co ze złożonością pamięciową??? Jak podobnie zrobić to dla wersji rekurencyjnej????

Pozdrawiam!

1

Zł. pamięciowa to O(n) (a dokładniej Theta(n)), bo masz tablicę f[0..n].

0

A czasową mam dobrze?

1

Tak.

0

A moglibyśmy jeszcze określić wspólnie złożoność czasową i pamięciową wersji rekurencyjnej??

int fib(int x)
{
if (x < 2)
return 1;
else
return fib(x-1) + fib(x-2);
}

Tutaj pętli nie ma, nie wiem niestety jak tutaj zacząć.

1

Jeśli f(n) to n-ta liczba Fibonacciego, to złożoność:

  • pamięciowa wynosi O(n) - na stos wywołań,
  • obliczeniowa wynosi O(f(n)) - bo algorytm rozbija f(n) na sumę jedynek,

PS. zakładam, że nie ma implicite spamiętywania.

0

W porządku, a jak mogę uzasadnić poprawność wersji iteracyjnej??

1

Przez indukcję.

0

TO może jaką równość lub nierówność mam udowodnić i już sobie poradzę :)

0

Przez indukcję, czyli najpierw udowodnij, że f[0] i f[1] są poprawne, a potem udowodnij, że dla każdego n >= 2, jeśli f[n - 2] i f[n - 1] są poprawne, to f[n] też jest poprawne.

0

Zrobione. Dzięki.

1 użytkowników online, w tym zalogowanych: 0, gości: 1