以下斐波那契数列的时间复杂度是什么

Question

我不知道它的O（n ^ 2）...根据我的图像，应该是O（n）

array[n];
array[0] = 1;
array[1] = 1;
for i = 2 to i = n:
   array[i] = array[i-1] + array[i-2]
return array[n]

Answer 1

您链接的图片不正确。该循环的每次迭代都需要O（1）的时间来执行，并且运行O（n）次，因此该循环的成本为O（n）。似乎幻灯片意外地将循环的O（n）总成本乘以O（n）迭代次数，从而错误地获得了O（n ²）项。

您的分析是正确的-该代码确实在时间O（n）上运行。