data-structures - 给定元素按递增顺序排序的数组，创建具有最小高度的 BST 的时间复杂度

Question

我试图通过两种方式解决这个问题。
最明显的解决方案是使用 BST 的标准插入操作，从根节点开始，递归进行。但是，要插入每个节点需要我 log N时间。由于我必须为 N 个节点做这件事，所以我完全需要 NlogN .
所以我想了如何切断几个调用，这样我就不需要遍历整个树来插入每个节点。
在这种方法中，在插入根之后，我只传递数组的一半(左半)来生成左子树和数组的右半部分(右半)来生成右子树。
它的代码如下:

public static TreeNode createMinBST(int arr[], int start, int end){
 if (end < start) {
 return null;
 }
 int mid = (start + end) / 2;
 TreeNode n = new TreeNode(arr[mid]);
 n.left = createMinBST(arr, start, mid - 1);
 n.right = createMinBST(arr, mid + 1, end);
 return n;
 }

这个，我很容易就上来了。但是我发现很难分析这段代码的运行时间。请问有什么帮助吗？
您能否也说明如何到达运行时，以便我可以将该分析重用于其他问题？

Answer 1

该算法运行时间为 O(n)。这里有两种方法可以看到这一点。

首先，您可以注意到对该函数的每次调用都在 O(1) 时间内运行，并且每次调用都会“用完”一个节点。这意味着总共只能有 O(n) 次调用，因此总工作量将是 O(n)。

或者，您可以使用主定理。您的函数执行 O(1) 工作并对大小(大约)n/2 的子数组进行两次调用，因此您会得到重复

T(n) = 2T(n / 2) + O(1)

根据主定理，这解决了 O(n)。

希望这可以帮助!