niezmienniki oraz zlozonosc alg

Popiolkas · Post autor: **Popiolkas** » 9 paź 2009, o 18:56

Witam, musze znalezc niezmiennik, oraz oszacowac zlozonosc algorytmu (wiem ze wynosi ona O(lgn)) ktory oblicz n-ty wyraz ciagu fibonnaciego.

tu jest moj kod napisany w javie, ale nie mam pojecia jak oszacowac zlozonosc i znalezc ten niezmiennik, z gory dzieki za pomoc, pozdr

Zordon · Post autor: **Zordon** » 9 paź 2009, o 19:03

Szybkie potęgowanie macierzy (podnoszenie do potęgi n) ma złożoność \(\displaystyle{ O(\lg n)}\), więc wystarczy to wykazać. A robi się to natychmiastowo po napisaniu rekurencji na szybkie potęgowanie.

Popiolkas · Post autor: **Popiolkas** » 9 paź 2009, o 20:27

a moglbys kolego mi to rozpisac?:) bo siedze nad tym juz 2 dzien i nei za bardzo mi to idzie:)