这个函数的时间复杂度是多少？

Question

我只是想弄清楚以下函数的时间复杂度是多少，我不确定它是 O(logn) 还是 O(nlogn)。

在此先感谢您的帮助！ :)

PD: 如果您能告诉我您回复的原因，我将不胜感激

def max_unimodal(arr):
  
  if len(arr) == 1:
    return arr[0]
  elif len(arr) == 2:
    return max(arr[0], arr[1])
  
  mid = len(arr) // 2
  
  max_left = max_unimodal(arr[:mid])
  max_right = max_unimodal(arr[mid:])

  return max(max_left, max_right)

Answer 1

重复次数为T(n) = 2T(N/2) +O(1)。 T(N) = O(N) 应该是显而易见的，无论是通过主定理（在这种情况下是矫枉过正），还是通过简单的扩展：

T(N) = 2T(N/2) + c +
       2(2T(N/4) + c) + c = 4T(N/4) + 3c = 
       4(2T(N/8) + c) + 3c = 8T(N/8) + 7c =
       ....
       = 2^kT(N/2^k) + 2^(k-1) c

一直到 2^k 大约 N，给

T(N) = (T(1) + c/2) * N

编辑：解决评论中的问题：

以上分析假设列表视图通过。在 Python 列表切片的文字实现中，复杂性要差得多。列表切片本身是 O(n)，递归变成 T(N) = 2T(N/2) +O(N)。尝试证明在这种情况下结果是~~O(N^2)~~O(N log N)（不知道自己在想什么），用同样的方法

这个函数的时间复杂度是多少？

What's the time complexity of this function?

algorithm

big-o

time-complexity