python - 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 可以忽略(渐进查看时无关紧要)。