Haskell中的整数时间复杂度

Question

我上周在学校做了一项任务,实现了计算斐波纳契数列中第n个数的函数."子指派"是使用累积(可能不是正确的翻译)来实现它,以便给出函数O(n)时间复杂度.这一切都很好,直到我尝试制作函数(Int - > Integer).通过实验,我意识到时间复杂度对于非常大的数字接近于O(n ^ 2).在我看来,这必须是因为Integer的实现,这使我对它的工作方式有点好奇.我做了一些谷歌搜索,没有找到任何看似有用的东西,所以我转向你们,希望得到一个解释或一个解释彻底的链接.

我的代码:

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"

我很感谢所有答案

尤

Answer 1

这与Haskell无关,这只是Fibonacci数量迅速呈指数增长的结果.具体而言,第n个斐波那契数已约(日志₂ φ)n或大致0.48的n位,其中φ是黄金比例(1 + SQRT 5)/ 2,由于除了k位整数的花费O(k)的时间,你的O (n)加法实际上总共需要O(n ^ 2)时间,因为平均而言,你添加的数字有O(n)位.

(注意粘贴:大O应该是上面的大Theta.)

Answer 2

要添加到Reid的答案,您的算法具有O(N)时间复杂度的事实取决于您认为是执行步骤.这是对时间复杂性的常见误解:时间复杂度始终与执行时间相对应.

要考虑的步骤取决于我们想要分析问题的深度.如果将步骤定义为Integer的一个加法,是的,带累加器的算法在O(N)时间内运行.如果将步骤定义为一个单词添加(32位或64位加法),则它将以O(N ^ 2)运行,如Reid所述.

如果您希望您的复杂性分析与执行时间相对应,则需要使用执行步骤,其执行时间以常量为界,例如添加两个处理器字.添加整数不是,因为整数可以任意大.