python – 一个while循环的大O.

发布时间：2020-12-20 11:46:45 所属栏目：Python 来源：网络整理

导读：我想知道这个代码片段的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循环中没有比较的值被减半.

我想知道这个代码片段的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循环中没有比较的值被减半.

解决方法

它是O(N ^ 2)：

> while循环需要N步,直到所有元素都被删除.> list.pop(0)是O(N);下面列表中的所有元素都必须向上移动一步.缩短列表每个步骤仍然会在整个过程中平均提供1/2 N步,其中1/2可以忽略(渐近查看时无关紧要).

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!