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

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 logn）。你知道吗

首先，考虑递归过程本身：分裂决策的最坏情况（对“复杂性”的默认解释）是什么？如果给定的数组被排序，那么最大的元素总是在最后，并且您的递归退化为在每次迭代中删除一个元素的过程。你知道吗

第二，考虑一次传递函数的复杂性，把递归放在一边。在你的序列中每个操作的复杂性是什么？你知道吗

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

其中许多是O（1）操作，但有几个是O（n）其中n是当前列表的长度，而不是原始列表的长度。你知道吗

这将导致最坏情况O（n^2）。最好的情况是O（n logn），根据您的直觉，给定一个完全平衡的树作为输入。一般情况下。。。你可能不再需要它了，但它是O（n logn）的，常数不太有利。你知道吗