时间双invarient for循环的复杂性复杂性、时间、invarient、for
我有列出的阵列（即阵列中的每个单元包含一个列表）。数组的长度 N 键，所有列表中的所有长度为 K
我想遍历所有的列表元素（全阵列中）：
的for（int i = 0;我n种; ++ I）{
对于（INT J = 0; J＆LT;数组[我] .list.Length（）; ++ j）条{
//做一些O（1）
}
}
注意的内循环运行不到 K 元外循环的迭代次数，但它总迭代所有的我是 K
问题请问的code的时间复杂度为O（n + k）的？还是会为O（N * K）？
解决方案问题请问的code的时间复杂度为O（n + k）的？还是会为O（N * K）？
都不是。
复杂度 O（N + K）。在这种情况下，其中 N'LT; = K ，这将等于 O（K），但这并不一定是案例。
N'LT; = K （原来的答案）
如果所有长度的总和 K ，然后，如果你没有在外环做别的，运行时间将 O（K）。 N 是无关紧要在这种情况下，由于没有什么有趣的你正在做的 N 次。您的数据恰好被分割在 N 块。
在平均，每个列表的大小是 K / N 。这使得该算法的时间复杂度 O（N * K / N）这将导致 O（K）。
N'GT;氏/ code>
在该在当n 比 k大， N 变得重要，因为工作每次都要做，即使它只是检查数组[我] 。正因为如此，在这种情况下，复杂度 O（N + K）。
更新
由于尔迪Vermeulen的正确地指出了意见，我原来的答案，只有考虑到的情况下 N'LT; = K 是不完全不正确。答案已经进行了相应的修改。
I have an array of lists(i.e. each cell in the array contains a list). The length of the array is n and the sum of all the lengths of all the lists is k
I want to iterate over all the list elements(in the whole array):
for(int i = 0; i < n; ++i) {
for(int j = 0; j < array[i].list.Length(); ++j) {
//do something in O(1)
}
}
NOTE the inner loop runs less than k times per an iteration of the outer loop, but the total iterations it does for all the i is k
QuestionDoes the time complexity of the code is O(n + k)? Or would it be O(n*k)?
解决方案Question Does the time complexity of the code is O(n + k)? Or would it be O(n*k)?
Neither.
The complexity is O(n + k). In the case where n <= k, this would equal O(k), but this is not necessarily the case.
n <= k (original answer)
If the sum of all lengths is k, then, if you don't do anything else in the outer loop, the running time would be O(k). n is irrelevant in this case, since there is nothing interesting you're doing n times. Your data just happens to be split up in n chunks.
On average, each list's size would be k/n. That makes the time complexity of the algorithm O(n * k/n) which results in O(k).
n > k
In the case that n is larger than k, n becomes relevant since work has to be done each time, even if it's only checking the Length() of array[i]. Because of that, in this case the complexity is O(n + k).
Update
As Jordi Vermeulen correctly points out in the comments, my original answer that only took into consideration the case where n <= k is incomplete incorrect. The answer has been edited accordingly.
