從排序後的數組創建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; 
}

來源

2017-10-28 Uzair Ahmed

讓我們嘗試一些蘇格拉底式的方法。大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)

這裏<或>表示多項式更小或更大。

來源

2017-10-28 14:27:36 coderredoc

它在O（n）中。的總時間被定義爲T（N）= 2T（N/2）+ C：

T（N）：採取大小爲n的數組時間
C：常數（查找的中間陣列和連接根到左右子樹需要一定的時間）

來源

2017-10-28 14:27:13

從排序後的數組創建BST的大哦

回答

相關問題