这个大O评估正确吗？

Question

我无法理解某些事情。我什至不确定它是否正确。

在Cracking the Code Interview中，有一节要求你确定一些函数的大O。在大多数情况下，它们是可以预测的。

然而，其中一个让我陷入困境。
显然，这评估为 O(ab):

void printUnorderedPairs(int[] arrayA, int[] arrayB) {
  for (int i = 0; i < arrayA.length; i++){
    for (int j = 0; j < arrayB.length; j++){
      for (int k = 0; k < 100000; k++){
         System.out.println(arrayA[i] + "," + arrayB[j]);
      }
    }
  }
}

有理说

"100,000 units of work is still constant, so the runtime is O(ab).

我想看看为什么这有道理，但我还做不到；自然地，我期望 O(abc).

是的，100,000 是一个常量，arrayA 和 arrayB 是数组，但是我们取数组的 length .在运行这些 for 循环时，array[x].length 不会是一个常数（假设数组的大小在执行期间不改变）？

所以，这本书是对的吗？如果是这样，我将非常感谢洞察力和直觉，这样我以后就不会陷入同样的陷阱。

谢谢！

Answer 1

作者所说的常量是指一个固定的值，无论输入大小如何，这与可能改变的输入数组的长度不同。例如，printUnorderedPairs 可能会使用不同的数组作为参数调用，并且这些数组可能具有不同的大小。

Answer 2

数组 A 和 B 的长度未指定，您所能做的就是给出作为这两个长度函数的复杂度的指示。给定代码中没有其他变量。

Answer 3

Time complexity is generally expressed as the number of required elementary operations on an input of size n, where elementary operations are assumed to take a constant amount of time on a given computer and change only by a constant factor when run on a different computer.

O(ab) 是上述情况的复杂度，因为 arrayA 和 arrayB 的长度是可变的，完全依赖于调用函数，而 100000 是常数，不会因任何外部因素而改变。

Complexity is the measure of Unknown

Answer 4

Big-O 的重点是检查计算如何随着输入的增长而增长。很明显，如果 A 加倍，它就会加倍，如果 B 加倍，它也会加倍。这两个是线性的。

您可能会感到困惑的是，您可以轻松地将 100k 替换为 C，这是另一个线性输入，但碰巧它没有将 100k 作为变量，它是一个常数。

在 Big-O 问题中，类似的事情是您单步执行固定次数的数组。这不会改变 Big-O。例如，如果您遍历一个数组以找到最大值，那就是 O(n)。遍历它两次以找到最小值和最大值......也是 O(n)。事实上，这与单步执行一次以在单次扫描中找到最小值和最大值是一样的。

这个大O评估正确吗？

Is This Big O Evaluation Correct?

algorithm

big-o