Witam
- Jak mam uzasadnić poprawność algorytmu dla ciągu Fibonacciego w wersji iteracyjnej??
- 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!