while循环的大O

Question

我想知道这段代码片段的 Big-O 是什么

def clear_list(my_list):
    while len(my_list) > 0:
        my_list.pop(0)
    return my_list

会是 O(n^2) 还是 O(n)，因为 while 循环是 O(n) 或 O(1)，pop(0) 也是 O(n)。我不认为 while 循环是 O(log n) 因为 while 循环中没有被比较的值被减半。

Answer 1

O(N^2):

while 循环执行 N 步，直到所有元素都被删除。
list.pop(0) 是 O(N)；以下列表中的所有元素都必须向上移动一级。列表被缩短的每一步仍然给你在整个过程中平均 1/2 N 步，其中 1/2 可以忽略（渐近地查看时无关紧要）。

Answer 2

它将是 O(n^2) 因为在 while 循环中你必须遍历所有 n 个元素，而在 pop 中你必须移动所有元素跟随第一个元素。

这里有一个 link 相关的回答： What is the time complexity of popping elements from list in Python?

Answer 3

我只是为你做了基准测试（编辑：我假设 return 放错了地方，否则我什至为什么要这么做）

from time import time
def check(size):
    a = range(size)
    start = time()
    clear_list(a)
    return time() - start
check(40000) # About .4 seconds on my computer
check(80000) # About 1.6 seconds on my computer

显然 O(n²)

while循环的大O

Big-O of a while loop

python

big-o

while-loop