Tam tersi zaman karmaşıklığı Haskell

Question

Geçen hafta okulda, fibonacci dizisindeki n: th sayısını hesaplamak için bir fonksiyon uyguladım. Bir 'alt görev', O (n) zaman karmaşıklığı sağlamak için birikimi kullanarak (doğru bir çeviri olmayabilir) uygulamalıydı. Bu, fonksiyonu yapmaya çalışana kadar iyi çalıştı (Int -> Tamsayı). Biraz deneyerek, zaman karmaşıklığının gerçekten büyük sayılara O (n^2) yakın olduğunu fark ettim. Bana bunun, bunun nasıl çalıştığına dair biraz merak uyandırdığı Tamsayı uygulaması nedeniyle olması gerektiği anlaşılıyor. Birkaç Google araması yaptım ve yararlı görünen bir şey bulamadım. Size bir açıklama veya iyice açıklayan bir bağlantı elde etmeyi umuyorlar.

Kodum:

ackfib 0 = 0 
ackfib 1 = 1   
ackfib n = loop n 1 0 1 
    where 
     loop n n1 n2 i 
      | i < n  = loop n (n1+n2) n1 (i+1) 
      | i == n = n1 
      | i > n  = error "n must be greater than or equal to 0" 

kendisini herkesin müteşekkirim

Answer 1

Bu gerçekten Haskell ile ilgisi yoktur, bu Fibonacci sayıları büyümek gerçeğinin sadece bir sonucudur

Viktor cevaplar katlanarak hızla. Spesifik olarak, fibonacci sayısı yaklaşık olarak (log φ) n'ye veya φ'un altın oranına (1 + sqrt 5)/2. olduğu 0.48 n bitine sahiptir. K-bit tam sayılarının eklenmesi O (k) zamanını aldığından, O (n) eklemeleriniz aslında toplam O (n^2) süreyi alır, çünkü ortalama olarak eklediğiniz sayıların O (n) bitleri vardır.

(Titizliği için not:. Büyük O gerçekten yukarıda büyük Teta olmalıdır)

Answer 2

Reid's answer eklemek için, algoritma O (N) saat karmaşıklığını olması, sen olarak kabul bağlıdır yürütme aşaması. Bu, zaman karmaşıklığı ile ilgili yaygın bir yanlış anlamadır: zaman karmaşıklığı her zaman yürütme süresine karşılık gelir.

Bu adımı göz önünde bulundurmak, sorunu ne kadar derinlemesine analiz etmek istediğimize bağlıdır. Bir adımı tamsayı olarak tanımlarsanız, evet, akümülatörler ile algoritmanız O (N) saatinde çalışır. Bir kelimeyi bir kelime olarak eklediyseniz (32 veya 64 bitlik bir ek), Reid'in açıkladığı gibi O (N^2) 'de çalışır.

Karmaşıklık çözümlemenizin yürütme süresine karşılık gelmesini istiyorsanız, yürütme zamanının bir sabit tarafından yukarıda iki yürütme sözcüğünün eklenmesi gibi bir yürütme adımı kullanmanız gerekir. Tamsayıların eklenmesi, çünkü Tam Sayılar keyfi olarak büyük olabilir.