python - 为什么第一个代码的复杂性高于第二个代码？

Question

追加具有恒定的时间复杂度 O(1)。Extend 具有 O(n) 复杂性，在我的情况下 k（要添加的元素数）=n-1。Insert 和 del 都有 O(n) 的时间复杂度。那么为什么第一个代码比第二个代码花费更长的时间？
1.第一段代码

def circularArrayRotation(a,n, queries):      
  for _ in range(n):
      arr=[]
      arr.append(a[-1])
      arr.extend(a[0:-1])
      a=arr          
  for j in queries:
      yield a[j] 

2. 第二段代码

def circularArrayRotation(a, n, queries):
    for _ in range(n):
        a.insert(0, a[-1])
        del a[-1]
    for j in queries:
        yield a[j]

标签： pythonalgorithmtime-complexity

Answer 1

我不是百分百确定。但我的假设是因为在您调用的第一个代码arr.extend(a[0:-1])中必须创建一个临时子列表。子列表的创建需要额外的时间。我会假设子列表的创建类似于子列表的大小O(M)在哪里。M

编辑：加上大 O，你有O(2N) = O(N). 但在实践中，这仍然会影响性能，只是没有其他任何东西那么重要。