双不变for循环的时间复杂度

Question

我有一个列表数组（即数组中的每个单元格都包含一个列表）。数组的长度为n，所有列表的所有长度之和为k

我想遍历所有列表元素（在整个数组中）：

for(int i = 0; i < n; ++i) {
    for(int j = 0; j < array[i].list.Length(); ++j) {
        //do something in O(1)
    }
}

注意每次外循环迭代运行的内循环少于 k 次，但它对所有 i 执行的总迭代次数是 k

问题代码的时间复杂度是O(n + k)吗？还是 O(n*k)？

Answer 1

你应该使用n*k。

Foreach cols, process each lines.

您必须对每一列 (n) 执行循环（for 或 foreach）。
然后在 n 循环内，您执行另一个循环（for 或 foreach）来处理每一行 (k)。

for (int i = 0; i < n; i++) {
   for (int j = 0; j < array[i].list.length(); j++) {
     // do something with array[i][j]
   }
}

Answer 2

对于外部循环的每个 i，内部循环是运行 array[i].list.Length() 你说的是 k:

k times + -+
k times +  |
...        |
...        +--- n times
...        |
k times   -+

所以得到的时间是O(n * k)

Answer 3

Question Does the time complexity of the code is O(n + k)? Or would it be O(n*k)?

~~都没有。~~

复杂度为O(n + k)。在 n <= k 的情况下，这将等于 O(k)，但情况不一定如此。

如果所有长度的总和是k，那么，如果你在外循环中不做任何其他事情，运行时间就是O(k)。 n 在这种情况下无关紧要，因为您所做的 n 次没有任何有趣的事情。您的数据恰好被分成 n 个块。

平均而言，每个列表的大小为 k/n。这使得算法的时间复杂度 O(n * k/n) 导致 O(k).

在 n 大于 k 的情况下，n 变得相关，因为每次都必须完成工作，即使它只是检查 Length() array[i]。因此，在这种情况下，复杂度为 O(n + k).

正如 Jordi Vermeulen 在评论中正确指出的那样，我最初的回答只考虑了 n <= k 是 ~~不完整~~ 的情况。答案已相应编辑。

Answer 4

这是O(n + k)，当n为O(k)时为O(k)。然而，情况不一定如此（正如 Bart van Nierop 在回答中所建议的那样）。例如，考虑 n = k² 的情况。循环仍然是运行 k² 次，所以你不能说复杂度是 O(k)，即使在许多迭代中除了增加之外不会做任何工作柜台.

Answer 5

O(k).do something part 会出现 k 次。 n 在这种情况下无关紧要。

Time complexity of double invarient for loops