Ciąg Fibonacciego

Odpowiedz Nowy wątek
2011-09-02 10:07
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]

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!

edytowany 3x, ostatnio: Poczatkujacy21, 2011-09-02 10:22

Pozostało 580 znaków

2011-09-02 10:23
1

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


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.

Pozostało 580 znaków

2011-09-02 10:50
0

A czasową mam dobrze?

Pozostało 580 znaków

2011-09-02 10:59
1

Tak.


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.

Pozostało 580 znaków

2011-09-02 11:03
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ąć.

Pozostało 580 znaków

2011-09-02 11:10
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.


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.
edytowany 1x, ostatnio: Wibowit, 2011-09-02 11:10

Pozostało 580 znaków

2011-09-02 11:14
0

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

Pozostało 580 znaków

2011-09-02 11:25
1

Przez indukcję.


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.

Pozostało 580 znaków

2011-09-02 11:29
0

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

Pozostało 580 znaków

2011-09-02 12:37
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.


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.

Pozostało 580 znaków

2011-09-02 12:41
0

Zrobione. Dzięki.

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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