[bebzimo_v2]

Czy ten algorytm jest optymalny oraz jak zmierzyć jego złożoność obliczeniową?

https://codeshare.io/5QONzQ

#programowanie #informatyka #pytanie

[a.....y]

złożoność obliczeniową

@bebzimo_v2: http://home.agh.edu.pl/~byrska/IC/10ZlozonoscObliczeniowa.pdf

[bebzimo_v2]

@adgebworthy: Dzięki przyda się. Ale jakby ktoś mógł napisać dwa zdania jak siedzi w temacie to bardzo mi to ułatwi zrozumienie problemu.

[P.....s]

@bebzimo_v2: Myślę, że na pewno nie jest optymalny bo ciąg jest zapisany w postaci rekurencyjnej, gdyby korzystać z postaci ogólnej ciągu byłoby dużo szybciej. No ale żeby o tym wiedzieć trzeba mieć pewne pojęcie o matematyce dyskretnej a nie wystarczy klepać kodu ;)

[M.....o]

No ale żeby o tym wiedzieć trzeba mieć pewne pojęcie o matematyce dyskretnej a nie wystarczy klepać kodu ;)

@Philopolemus_Fronius: xD

[A.....t]

@bebzimo_v2 nie jest, na n liczbę fibonacciego jest wzór, taki z pierwiastkami z 5, ale przy większych liczbach będzie problem że względu na operacje na floatach
Jak chcesz prosty i lepiej działający od twojego to podobny tylko iteracyjny

[bebzimo_v2]

@Philopolemus_Fronius: Bardzo prawdziwa rada :)

[P.....s]

@bebzimo_v2: Możesz skorzystać ze wzoru Bineta. Wtedy obliczysz dowolny element ciągu fibonacciego nie korzystając z żadnej pętli :)

@MMurzinio: Taka prawda xD

[Minemaniak1]

@Philopolemus_Fronius: Przy większych elementach niedokładność liczb zmiennoprzecinkowych da się we znaki. W tym przypadku dużo lepiej użyć szybkiego potęgowania macierzy, otrzymujemy dowolny wyraz ciągu Fibbonaciego w złożoności O(logn).

[bebzimo_v2]

@Minemaniak1: @AwizisieAkat: @Philopolemus_Fronius: takie coś mi wyszło

[M.....o]

@bebzimo_v2: No taki algorytm ma nieskończenie małą złożoność, należy się jakiś medal Fieldsa. ( ͡° ͜ʖ ͡°)