为什么 O(n^2) 与 O(ab) 不同？

Question

我的问题是 O(n^2) 与 O(ab) 之间的区别是什么。嵌套的 for 循环中有两个不同的 N 数组。从 CTCI 中，我读到它不是 O(N^2) 而不是 O(ab)，因为它有不同的输入。for (int i = 0; i < arrayA.length; i++) {    for (int j = 0; j < arrayB.length; j++) {    }}

Answer 1

很简单的：

因为做类似 (a) 1 x (b) 1000 万……只需要 1000 万个“时隙”。

而 (n) 1000 万 x (n) 1000 万……好吧，那总是 n*n，不是吗。

换句话说：O(ab) 表示您有两个决定复杂性的参数。O(n^2) 表示您的复杂性仅取决于一个参数。

Answer 2

为什么 O(n^2) 与 O(ab) 不同？

O(n^2)转化为O(n*n)，其复杂度仅取决于 1 个变量。您的示例取决于 2 个独立变量，因此复杂性不一定是这两个变量中的任何一个的二次方。例如，如果您有一个非常小b和一个非常高的a，那么您的复杂度几乎与 a 成线性关系。

这两个表达式相等的唯一情况是 when n = a = b, thenO(n^2) = O(a*b)将适用。

Answer 3

如果 a 和 b 的长度相同，则为 O(n^2)，否则为 O(ab)

Answer 4

因为它取决于应用程序/输入的属性。

如果 a 或 b 保持较低或恒定，则 O(ab) 的缩放比例类似于 O(n) 而不是 O(n^2)。