时间戳

首页 > 解决方案 > 计算算法的复杂度（Big-O）

python - 计算算法的复杂度（Big-O）

问题描述

我目前正在围绕 Big-O 复杂性和计算算法的复杂性做一些工作。

我似乎在努力制定计算复杂性的步骤，并正在寻找一些帮助来解决这个问题。

功能：

index = 0
    while index < len(self.items):
        if self.items[index] == item:
            self.items.pop(index)
        else:
            index += 1

实际的挑战是重写此函数，使其具有 O(n) 最坏情况复杂度。

我的问题是，据我所知，赋值语句和 if 语句的复杂度为 O(1)，而 while 循环的复杂度为 (n)，在最坏的情况下，while 循环中的任何语句都可以执行 n次。所以我把这个作为1 + n + 1 = 2 + n = O(n)

我想我一定是错误地解决了这个问题，否则重写函数是没有意义的。

对此的任何帮助将不胜感激。

标签： pythontime-complexitybig-o

解决方案

如果 self.items 是一个列表，那么 pop 操作的复杂度为“k”，其中 k 是索引，所以这不是 O(N) 的唯一方法是因为 pop 操作。
可能完成练习是为了让您使用其他一些迭代和从列表中删除的方法。

要使其成为 O(N)，您可以执行以下操作：

self.items = [x for x in self.items if x == item]

推荐阅读