algorithm - 嵌套算法的计算复杂度

Question

给定一个数组 a [1,2,3,4,5,6,7,8,9,10] 假设我们有一个执行以下操作的算法：

for i in 0..a.length
  for j in 0..a.length
    ...

这将具有 O(n^2) 的 Big O 运行时间，因为对于每个元素，它将遍历整个数组。

但是如果内部循环只从外部索引向前遍历呢？

for i in 0..a.length
  for j in i..a.length
    ...

也就是说，相比之下，第一个算法将在每次迭代（外循环）时查看 n 个元素。第二个算法着眼于：

在为这种算法计算 Big O 运行时间时，它仍然是 O(n^2) 吗？

score 10 · Accepted Answer

这仍然是 O(n^2)。和 1 + 2 + ... + n 为 n(n+1)/2，即 O(n^2)。

更一般地，对于任何多项式函数 p(n)，p(1) + p(2) + ... + p(n) 的总和为 O(np(n))。这个证明要困难得多，因为你必须推理 n 的任意幂的总和，但它确实是真的。这意味着，例如，如果您将第三个循环嵌套在从 j 到 n 的内部循环之外，则运行时间将为 O(n^3)。

score 0 · Accepted Answer

如果给定 a 是那个特定的数组，那么该算法的时间复杂度是恒定的（或 O(1)）。也许我从字面上读了你问的内容，但是对于 O(n^2) 的最严格限制，a 必须是像 [1,2,...,n] 这样的数组。如果 a 的大小明确为 10，则算法始终以相同的步数运行。

希望这个答案是不必要的，但我是离散数学课的助教，我们经常给出与此非常相似的技巧问题。如果我误解了这个问题，那么我为浪费您的时间而道歉！另外，已经发布的答案非常好！

2 回答 2