嵌套算法的计算复杂性

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个元素.第二个算法着眼于:

• 第一次迭代时的n个元素
• 第二次迭代中的n-1个元素
• 第三次迭代中的n-2个元素
• ...
• 最后一次迭代的1个元素

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

Answer 1

这仍然是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).