从排序数组创建 BST 的大 Oh

Question

我编写了这个方法来将我拥有的排序数组转换为平衡二叉搜索树。我不确定这种方法的大 O 时间复杂度应该是多少。会是 O(n) 吗？

Node ArrayToBST(Node arr[], int start, int end) 
{
    if (start > end) 
        return null;
    int mid = (start + end) / 2;
    Node node =arr[mid]; 
    node.left = ArrayToBST(arr, start, mid - 1);
    node.right = ArrayToBST(arr, mid + 1, end);
    return node;
}

Answer 1

复杂度为O(n)。总时间定义为 T(n) = 2T(n/2) + C:

T(n)：大小为 n
C: 常量（找数组的中点和连接根到左右子树需要常量时间）

Answer 2

复杂度为 O(n)。每个节点都被创建，所以会有 n 次调用......每个都有 O(1) 运行时间。

T(n)=2T(n/2)+C如果你使用大师定理，你会得到相同的结论。

大师定理规则：-

如果n^(log b base a) < f(n)那么T(n) = f(n)
如果n^(log b base a) = f(n)那么T(n) = f(n) * log n
如果n^(log b base a) > f(n)那么T(n) = n^(log b base a)

`n` -> input size
`a` -> number of subproblems
`n/b` -> size of each subproblem
`f(n`) -> cost of non-recursive calls (Here C)

这里

a = 2, b = 2, f(n) = O(1)

n^(log b base a) = n = O(n)

此处<或>表示多项式更小或更大

从排序数组创建 BST 的大 Oh

Big Oh of creating a BST from a sorted array

java

algorithm

binary-search-tree

asymptotic-complexity