python - 复杂度与运行时间的实际增长不匹配？ (Python)

Question

我在 python 中运行了 2 个代码，然后测量了完成所需的时间。代码非常简单，只是递归最大值。这里是: 1.

def max22(L, left, right):
  if(left>=right):
    return L[int(left)]
  k = max22(L,left,(left+right-1)//2)
  p = max22(L, (right+left+1)//2,right)
  return max(k,p)


def max_list22(L):
  return max22(L,0,len(L)-1)

---

def max2(L):
  if len(L)==1:
    return L[0]
  l = max2(L[:len(L)//2])
  r = max2(L[len(L)//2:])
  return max(l,r)

---

第一个应该在 O(logn) 中运行 (imo)，第二个在 O(n*logn) 中运行。 但是，我测量了 n=1000 、 n=2000 和 n=4000 的运行时间， 不知何故，这两种算法的增长似乎都是线性的!这怎么可能？我是否弄错了复杂性，或者可以吗？ 谢谢。

Answer 1

第一个算法不是 O(log n) 因为它检查每个元素的值。可能显示为O(n)

至于第二个，可能您只是没有注意到 n 和 nlogn 在如此小的尺度上的区别。