用于迭代列表中步骤的 Big-O 表示法 -Python

Question

我希望遍历列表中的每三个元素。但是在考虑 Big-O 表示法时，Big-O 复杂度是 O(n)，其中 n 是列表中元素的数量，还是每三个元素为 O(n/3)？

换句话说，即使我指定列表只应每隔三个元素迭代一次，Python 是否仍在遍历整个列表？

示例代码：

def function(lst):
    #iterating over every third list
    for i in lst[2::3]:
        pass

Answer 1

使用 Big-O 表示法时，我们忽略函数前面的任何标量倍数。这是因为该算法仍然需要“线性时间”。我们这样做是因为 Big-O 符号考虑了算法在扩展到大输入时的行为。

这意味着无论算法是考虑列表中的每个元素还是每隔三个元素，时间复杂度仍然与输入大小成线性关系。例如，如果输入大小加倍，则无论您查看每个元素还是每隔三个元素，执行时间都会加倍。

数学上我们可以这么说是因为定义中的 M 项 (https://en.wikipedia.org/wiki/Big_O_notation):

abs(f(x)) <= M * O(f(x))

Answer 2

这里的大 O 表示法将保持为 O(n)。

考虑以下因素：

n = some big number
for i in range(n):
  print(i)
  print(i)
  print(i)

做 3 个动作算 O(3n) 还是 O(n)？在）。执行三个动作而不是一个动作会降低现实世界的性能吗？绝对！

大O表示法是看函数的增长率，而不是物理运行时间。

考虑 pandas 库中的以下内容：

# simple iteration O(n)
df = DataFrame([{a:4},{a:3},{a:2},{a:1}])
for row in df:
  print(row["a"])
# iterrows iteration O(n)
for idx, row in df.iterrows():
  print(row["a"])
# apply/lambda iteration O(n)
df.apply(lambda x: print(x["row"])

所有这些实现都可以被认为是 O(n)（常量被删除），但这并不一定意味着运行时是相同的。其实方法3应该比方法1快800倍左右(https://towardsdatascience.com/how-to-make-your-pandas-loop-71-803-times-faster-805030df4f06)!

另一个可能对您有帮助的答案：Why is the constant always dropped from big O analysis?

用于迭代列表中步骤的 Big-O 表示法 -Python

Big-O Notation for iteration over steps in list -Python

python

big-o