for 循环嵌套在 while 循环中的时间复杂度
Time complexity with for loop nested in while loop
这个算法的时间复杂度是多少？
while len(array) > 0:
for item in array:
do stuff to determine which item to pop
array.pop(item_to_pop)
我的第一直觉是 O(N^2)。但是，如果我每次执行 while 条件时都将数组大小减半，它将是 O(n)。我猜每次迭代将我的数组大小减少 1 不会产生相同的效果？
- 如果在外循环中将数组的大小减一，则外循环中有
n 次迭代，对于每次外循环迭代，最多有 n 内循环迭代。所以，通过简单的时间复杂度计算，这是O(n^2)个过程。
[n + n-1 + n-2 + .... + 1 = n(n-1)/2]
- 如果在外循环中每次都将数组大小减半，那么最多有
log(n)次迭代。并且对于每个外循环，最多有 n 次内循环迭代。所以，时间复杂度是 O(n log(n)).
[n + n + n + .... n(lg(n)) ~= 2n ~= 2^(lg(n)+1) ]
这个算法的时间复杂度是多少？
while len(array) > 0:
for item in array:
do stuff to determine which item to pop
array.pop(item_to_pop)
我的第一直觉是 O(N^2)。但是，如果我每次执行 while 条件时都将数组大小减半，它将是 O(n)。我猜每次迭代将我的数组大小减少 1 不会产生相同的效果？
- 如果在外循环中将数组的大小减一，则外循环中有
n次迭代，对于每次外循环迭代，最多有n内循环迭代。所以，通过简单的时间复杂度计算，这是O(n^2)个过程。
[n + n-1 + n-2 + .... + 1 = n(n-1)/2] - 如果在外循环中每次都将数组大小减半，那么最多有
log(n)次迭代。并且对于每个外循环，最多有n次内循环迭代。所以，时间复杂度是O(n log(n)).
[n + n + n + .... n(lg(n)) ~= 2n ~= 2^(lg(n)+1) ]