Big Oh des Erstellens einer BST aus einem sortierten Array

Question

Ich habe diese Methode geschrieben, um ein sortiertes Array, das ich habe, zu einem ausgewogenen binären Suchbaum zu konvertieren. Ich bin nicht sicher, was die große O-Zeit-Komplexität dieser Methode sein sollte. Wäre es 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

Die Komplexität wird O(n) sein. Jeder Knoten wird erstellt, so dass es n Aufrufe gibt, die jeweils eine O (1) Laufzeit haben.

T(n)=2T(n/2)+C Wenn Sie Masters Theorem verwenden, werden Sie zu der gleichen Schlussfolgerung kommen.

Master-Satz Regeln: -

1. Wenn n^(log b base a) < f(n) dann T(n) = f(n)
2. Wenn n^(log b base a) = f(n) dann T(n) = f(n) * log n
3. Wenn n^(log b base a) > f(n) dann 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) 

Hier

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

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

Hier < oder > bezeichnet polynomial kleiner oder größer.

Answer 2

Es ist in O (n). Die Gesamtzeit wird als T (n) definiert = 2T (n/2) + C:

• T (n): Zeit für ein Array der Größe n genommen
• C: Konstante (Finding Mitte Array und Verknüpfung Wurzel zu linken und rechten Unterbäumen nehmen konstante Zeit)