временная сложность построения BST с использованием предварительного заказа

Question

Я попытался написать программу для построения двоичного дерева поиска с использованием последовательности предварительного порядка. Я знаю, что существует множество решений: алгоритм min/max, классическая (или «очевидная» рекурсия) или даже итерация, а не рекурсия.

Я попытался реализовать классическую рекурсию: первым элементом обхода предзаказов является корень. Затем я ищу все элементы, которые меньше, чем корень. Все эти элементы будут частью левого поддерева, а остальные значения будут частью правого поддерева. Повторяю это, пока не построю все подстроки. Это очень классический подход.

Вот мой код:

public static TreeNode constructInOrderTree(int[] inorder) { 
    return constructInOrderTree(inorder, 0, inorder.length-1); 
} 

private static TreeNode constructInOrderTree(int[] inorder, int start, int end){ 
if(start>end){ 
     return null; 
} 

int rootValue = inorder[start]; 
TreeNode root = new TreeNode(rootValue); 

int k = 0; 
for (int i =0; i< inorder.length; i++){ 
    if (inorder[i]<= rootValue){ 
     k=i; 
    } 
} 

root.left = constructInOrderTree(inorder, start+1, k); 
root.right= constructInOrderTree(inorder, k+1, end); 

    return root; 
    } 

Мой вопрос: Какова временная сложность этого алгоритма? Это O (n^2) или O (n * log (n))?

Я искал здесь, в stackoverflow, но нашел много противоречивых ответов. Иногда кто-то говорил, что это O (n^2), иногда O (n * log (n)), и я действительно запутался.

Можем ли мы применить здесь основную теорему? Если да, «возможно», мы можем считать, что каждый раз, когда мы делим дерево на два поддерева (равных частей), мы будем иметь отношение: (O (n) - сложность поиска в массиве)

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

Это даст нам сложность O(n*log(n)). Но на самом деле это не так, я думаю, мы не делаем делим дерево на равных частях, потому что мы ищем в массиве, пока не найдем адекватные элементы нет?

Можно ли применить здесь основную теорему?

Answer 1

Forethoughts:

Нет, это ни O(n^2), ни O(nlogn) в туалет. Из-за природы деревьев и того факта, что вы не выполняете никаких сложных действий над каждым элементом. Все, что вы делаете, это вывести его, в отличие от его сортировки с помощью некоторого алгоритма сравнения.

Тогда туалет будет O(n).

То есть, когда дерево перекошено, то есть одно из поддеревьев корня пуст. Тогда у вас есть простой связанный список. Затем, чтобы вывести его, вы должны посетить каждый элемент хотя бы один раз, указав O(n).

Доказательство:

Давайте предположим, что правое поддерево пусто, и за вызов усилия постоянен (только распечатать). Тогда

T(n) = T(n-1) + T(0) + c 
T(n) = T(n-2) + 2T(0) + 2c 
. 
. 
T(n) = nT(0) + nc = n(T(0) + c) 

С T(0) и c постоянные, вы в конечном итоге в O(n).