使用 O-notation 找到最坏情况下的运行时间

Question

我是 O 表示法的新手，我正在尝试使用这些给定范围的大 O 表示法来确定最坏情况运行时间的最紧边界：

O(1)
O(log n)
O(n)
O(n log n)
O(n**2)
O(n**3)
O(2**n) 作为实践，我在我所有代码的注释中添加了最严格的界限，但我无法弄清楚哪些情况会与抽象列表函数一起使用。例如，我在下面有两个简单的代码来求和：

示例：

def sums1(L):
  even = list(filter(lambda x: x%2==0, L))
  odd = list(filter(lambda x: x%2==1, L))
  return even + odd

def susm2(L):
  if L == []: 
    return 0
  s1 = sum(L)
  s2 = sums2(L[1:])
  s3 = sums2(L[2:])
  return s1+s2+s3

根据我的理解，第一个代码将运行 O(n^2) 次，因为要添加两个抽象列表，第二个代码将运行 O(2^n)。但是，我无法在网上找到任何类似的代码来查看我对此是否正确，所以我想在这里问一下。非常感谢任何关于运行的次数的指导。 :D

Answer 1

关于sums1，我相信你会有O(n)的复杂度，其中n是L中的元素个数。详细说明：

def sums1(L):
    even = list(filter(lambda x: x%2==0, L)) # O(n)
    odd = list(filter(lambda x: x%2==1, L))  # O(n)
    return even + odd                        # O(n)

创建 odd 和 even 列表每个都需要 O(n)，因为您需要遍历 L 两次。

连接两个列表，odd 和 even 也是线性的，O(n)。因为要连接两个列表，在最坏的情况下你必须遍历第一个，直到找到它的最后一个元素。

使用 O-notation 找到最坏情况下的运行时间

finding the worst-case runtime using O-notation

python-3.x

algorithm

runtime

big-o

computer-science