python O（n logn）算法的时间复杂度

Question

给定一个列表，假设“x”的长度是n，那么下面的算法的时间复杂度是多少？在

def foo(x):
  n = len(x)
  if n <= 1:
     return 17
  return foo(x[:n//2]) + foo(x[n//2:])

答案是：

O(n log n)

但我不明白为什么？ 我很难找出我们使用递归的最后一行，我知道它每次都会把列表的长度减半，所以它是O（logn），但它在每次迭代中都添加了另一个递归，每次也是O（logn），所以我想它的O（logn logn），但不幸的是不是。在

Answer 1

你正确地识别了它是O（logn），但是你没有识别出它是什么。它是达到基本情况所需的步骤数。因为每次将列表切成两半，每次调用foo，您使用的是一个只有刚才列表大小一半的列表。因此，需要O（logn）步骤来达到基本情况。在

下一个问题是：每一步要做多少工作？在第一步中，列表被分成两半，这需要n个内存副本。在第二步中，两个n/2大小的列表被分成两半。工作量不变！从一个步骤到下一步，您要剪切的每个列表的大小（由于调用foo(n//2)），但是您必须为执行此操作的列表的数量加倍（因为您递归地调用了foo）。因此，对于每一步，你总是在做O（n）功。在

O（logn）步骤*O（n）每个步骤的功=O（n logn）总计。在

Answer 2

这类似于合并排序。这里需要O（n）时间来分割数组as seen here，然后对列表的两部分执行操作。合并排序的时间复杂度为O（nlog（n））。在

如果您想派生merge sort，可以看一下this

Answer 3

这个算法为列表中的每个元素返回一次O(n)，然后它还实现了一个二等分搜索O(log n)，因此，O(n log n)

But I can't figure out why? I struggle to figure the last row where we use recursion, I know that it's cutting the length of the list in half each time so its O(log n), but it add's to each iteration the other recursion which is also O(log n) each time so I though its O(log n log n) but unfortunately its not.

O(log n) + O(log n)=O(log n)

在这上面添加一两个print语句会有很大帮助：

def foo(x):
    n = len(x)
    print(x)
    if n <= 1:
        print("return")    
        return 17
    return foo(x[:n//2]) + foo(x[n//2:])

>>> foo([1,2,3,4,5,6,7,8])
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4]
[1, 2]
[1]
Return
[2]
Return
[3, 4]
[3]
Return
[4]
Return
[5, 6, 7, 8]
[5, 6]
[5]
Return
[6]
Return
[7, 8]
[7]
Return
[8]
Return

这显然是为列表中的每个元素返回一次，这使得它至少是O(n)。另外，要在对分搜索类型方法中拆分列表，需要O(log n)