为什么时间复杂度被计算为O(n ^ 2)而不是O(n)?FibList(n) array[0-n] Create Array O(n) F[0] <- 0 O(1) F[1] <- 1 O(1) for i from 2 to n O(n) F[i] <- F[i-1] + F[i-2] O(n) return F[n] O(1)O(n)+O(1)+O(1)+O(n)O(n)+O(1)=O(n^2) 最佳答案 如果您假设将一个整数加上一个0到0的整数,而与该值成比例的话,它的值与max(k1, >)(即所谓的“比特”成本模型,或“对数”成本模型)成正比,那么所生成的代码的时间复杂度是O(n = 2)。这是因为F(i)几乎与phi^i成正比,其中phi是黄金比例这意味着f(i)有~i位。因此,成本:for i from 2 to n F[i] <- F[i-1] + F[i-2]与(1+2+3+……是n(n-1)/2,因此是o(n^2)。如果假设任意大小整数的加法为o(1),则代码为o(n)。有关成本模型的背景信息,请参见wikipedia上的本节这里必须小心,例如,有些分析认为一步加两个数。这个假设可能不是在某些情况下有保证的。例如,如果一个计算可以是任意大的,一个加法不能再假定为常数。顺便说一下,在你的问题中使用的方法,写出每一行的最大复杂度,然后乘以嵌套,并不是计算紧束缚复杂度的有效方法,尽管它在所有的复杂性都是多项式的情况下是有效的,在这种情况下它们是多项式。
09-10 10:03
查看更多