如何计算递归函数的时间和空间复杂性

Question

我目前正在练习一道面试题。问题是：

Given an integer array with no duplicates. A maximum tree building on this array is defined as follow: 
1. The root is the maximum number in the array. 
2. The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.
3. The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.
Construct the maximum tree by the given array and output the root node of this tree. 

我对这个问题的解决方案是：

def constructMaximumBinaryTree(nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
if nums:
maxIdx = nums.index(max(nums))
root = TreeNode(nums[maxIdx])
left = constructMaximumBinaryTree(nums[:maxIdx])
right = constructMaximumBinaryTree(nums[maxIdx + 1:])
root.left = left
root.right = right
return root

我知道它是如何工作的，但我不知道如何计算时间和空间的复杂性。如果我试图绘制出解决方案，输入数组会被一分为二，每个节点都会被拆分，直到它变空。所以，我猜它会是类似O(log n)的东西，但我不确定确切的推理。空间复杂性也是如此。有什么建议吗？

Answer 1

不，它不一定是O(n log n)。

首先，考虑递归过程本身：分裂决策的最坏情况("复杂性"的默认解释)是什么？如果给定的数组是排序的，那么最大元素总是在最后，你的递归退化为每次迭代删除一个元素的过程。

其次，考虑一次通过函数的复杂性，不考虑递归。您的序列中每个操作的复杂性是多少？

• 查找列表的max
• 在列表中查找元素
• 构造节点
• 切片列表
• 函数全部
• 切片列表
• 函数调用
• 任务
• 任务
• 返回根节点

其中许多是O(1)运算，但也有一些是O(n)--其中n是当前列表的长度，而不是原始列表的长度。

这会导致最坏的情况O(n^2)。最佳情况是O(n log n)，正如您所直觉的，给定一个完美平衡的树作为输入。一般情况。。。您可能不再需要它了，但它是O(n-logn)，具有不太有利的常数。