Временная сложность построения 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))?

Я искал здесь в stackru, но я нашел много противоречивых ответов. Иногда кто-то говорил, что это 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),