ALG7

3.8. Zadania 77

b)    T(n²) e 0(«³);

c)    7’(2"^+l) e 0(2");

d)    r((n + l)!) e 0(«!);

e)    7'(«)eO(n)=»{7(«)}'eO(/t^:);

f)    Twój własny przykład?

Zad. 3-2

Jednym z analizowanych już wcześniej przykładów był tzw. ciąg Fibonnaciego. Funkcja obliczająca elementy tego ciągu jest nieskomplikowana:

int fib(int n)

l

if (n==C)

return 1;

el se

lf (n~l)

return 1;

else

return fib(n-1)+fib(n-2);

)

Proszę określić, jakiej klasy jest to funkcja.

Zad. 3-3

Proszę przeanalizować jeden ze swoich programów, taki, w którym jest dużo wszelkiego rodzaju zagnieżdżonych pętli i tego rodzaju skomplikowanych konstrukcji. Czy nie dałoby się go zoptymalizować w jakiś sposób?

Prz4vkładowo często się zdarza, że w pętlach są inicjowane pewne zmienne i to za każdym przebiegiem pętli, choć w praktyce wystarczyłoby je zainicjować tylko raz. W takim przypadku „sporną” instrukcję przypisania „wyrzuca się” przed pętlę, przyspieszając jej działanie. Podobnie odpowiednio układając kolejność pewnych obliczeń, można wykorzystywać częściowe wyniki, będące rezultatem pewnego bloku instrukcji, w' dalszych blokach - pod warunkiem oczywiście, że nie zostały „zamazane” przez pozostałe fragmenty programu. Zadanie polega na obliczeniu złożoności praktycznej naszego programu przed i po optymalizacji i przekonaniu się „na własne oczy" o osiągniętym (ewentualnie) przyspieszeniu.

L