复杂性与运行时间的实际增长不匹配？（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（n），所以您的测试表明这一点并不奇怪。第二个算法是O（n*login），但如果使用正确的数组而不是列表，则会是O（n）。由于Python内置列表操作非常快，您可能还没有达到对数速度的减慢；请尝试使用类似于n=4000000的值，看看您得到了什么。你知道吗

请注意，如果可以并行运行两个递归调用（使用O（1）切片），那么两个算法都可以在O（logn）时间内运行。当然，你需要O（n）处理器来实现这一点，但是如果你在设计一个芯片，而不是编写一个程序，这种扩展将是简单的。。。你知道吗

Answer 2

仅仅因为一个函数将搜索空间除以2，然后递归地查看每一半，并不意味着它在复杂性中有一个log（n）因子。你知道吗

在您的第一个解决方案中，您将搜索空间拆分为2，然后最终检查每一半中的每个元素。与丢弃一半搜索空间的二进制搜索不同，您检查的是两部分。这意味着在搜索过程中不会丢弃任何东西，最终会查看每个元素，使复杂性为O（n）。第二个实现也是如此。你知道吗

Answer 3

第一种算法不是O(log n)，因为它检查每个元素的值。可以证明它是O(n)

至于第二个，你可能只是在这么小的范围内没有注意到n和nlogn之间的区别。你知道吗