从排序后的数组创建BST的大哦

问题描述：

我已经写了这种方法来将我有的排序数组转换为平衡二叉搜索树。我不确定这种方法的大时间复杂性应该是什么。它会是O（n）吗？从排序后的数组创建BST的大哦

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; 
}

让我们尝试一些苏格拉底式的方法。大O的目的是什么？如其中，它的定义是什么？它是用给定输入完成算法的时间的度量。通常以输入n来衡量。对？你触摸了多少次arr []中的所有元素？ – R4F6

答

复杂度将是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)

这里<或>表示多项式更小或更大。

答

它在O（n）中。的总时间被定义为T（N）= 2T（N/2）+ C：

T（N）：采取大小为n的数组时间
C：常数（查找的中间阵列和连接根到左右子树需要一定的时间）

从排序后的数组创建BST的大哦

相关推荐