algorithm - 双不变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

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) ，但不一定如此。

n <= k (原始答案)

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

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

n > k

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

更新

作为Jordi Vermeulen在评论中正确指出，我原来的回答只考虑了 n <= k 的情况不完整不正确。答案已相应编辑。