algorithm - 这个大 O 评估是否正确？

Question

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

在破解代码面试中，有一个部分要求您确定许多功能的大 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 个工作单位仍然是恒定的，所以运行时间是O(ab)。

我试图看看为什么这可能有意义，但我还不能；自然，我预料到了O(abc)。

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

那么，这本书对吗？如果是这样，我真的很感激洞察力和直觉，这样我以后就不会陷入同样的​​陷阱。

谢谢！

标签： algorithmbig-o

Answer 1

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