"addition" 的大 O 符号

Question

我正在 Coursera 上学习有关大 O 表示法的课程。看了一个斐波那契算法（非递归法）大O的视频，是这样的：

Operation                     Runtime
create an array F[0..n]        O(n)
F[0] <-- 0                     O(1)
F[1] <-- 1                     O(1)
for i from 2 to n:             Loop O(n) times
  F[i] <-- F[i-1] + F[i-2]     O(n) => I don't understand this line, isn't it O(1)?
return F[n]                    O(1)
Total: O(n)+O(1)+O(1)+O(n)*O(n)+O(1) = O(n^2)

除了 F[i] <-- F[i-1] + F[i-2] O(n) 之外的所有部分我都理解 => 我不理解这一行，不是 O(1) 因为它只是一个简单的加法吗？和F[i] <-- 1+1一样吗？

他们给我的解释是：但是加法有点差。通常加法是常数时间。但这些都是大数。记住，第 n 个斐波那契数大约有 n 个大于 5数字，它们非常大，而且它们通常不适合机器字。"

“现在，如果你想想如果你把两个非常大的数字加在一起会发生什么，这需要多长时间？好吧，你把十位数加起来，然后进位，然后加上百位数，你进，加上千位，你进等等等等。你必须为每个数字的位置做工作。因此，您所做的工作量应该与位数成正比。在这种情况下，位数与 n 成正比，因此这应该花费 O(n) 时间到运行那行代码。

我还是有点糊涂。这是否意味着大量也会影响时间复杂度？例如 a = n+1 是 O(1) 而 a = n^50+n^50 不再是 O(1)？

Video link 对于任何需要更多信息的人（4:56 到 6:26）

Answer 1

Big-O 只是一种用于跟踪数量级的符号。但是当我们在算法中应用它时，我们必须记住“什么数量级”？在这种情况下，它是“花费的时间”。

CPU 被设置为在恒定时间内对基本算术类型执行基本算术。对于大多数目的，我们可以假设我们正在处理这些基本类型。

然而，如果 n 是一个非常大的正整数，我们不能假设。一个非常大的整数将需要 O(log(n)) 位来表示。其中，无论我们将其存储为位、字节等，都需要一个 O(log(n)) 的数组来存储。（我们需要的字节数少于位数，但这只是一个常数。）当我们进行计算时，我们必须考虑我们将实际对该数组做什么。

现在假设我们正在尝试计算 n+m。我们将需要生成一个大小为 O(log(n+m)) 的结果，它必须至少花费那个时间来分配。幸运的是，小学的长加法，即你添加数字并跟踪进位，可以适用于大整数库，并且 O(log(n+m)) 可以跟踪。

因此，当您查看加法时，答案大小的对数才是最重要的。因为 log(50^n) = n * log(50) 这意味着 50^n 的操作至少是 O(n)。（得到50^n可能需要更长的时间...）这意味着计算n+1需要时间O(log(n))。

现在对于斐波那契数列，F(n) 大致是 φ^n 其中 φ = (1 + sqrt(5))/2 所以 log(F(n)) = O(n).

"addition" 的大 O 符号

Big O notation of "addition"

algorithm

big-o

add

fibonacci

time-complexity