Будет ли этот алгоритм работать в O (n)?

Question

Примечания: Это проблема 4,3 из Крекинг кодирвоания Интервью 5th Edition

Проблема: Учитывая отсортированный (порядок возрастания) массив, написать алгоритм для создания бинарного дерева поиска с минимальной высотой

Вот мой алгоритм, написанный на Java, чтобы сделать эту проблему

public static IntTreeNode createBST(int[] array) { 
     return createBST(array, 0, array.length-1); 
    } 
    private static IntTreeNode createBST(int[] array, int left, int right) { 
     if(right >= left) { 
      int middle = array[(left + right)/2; 
      IntTreeNode root = new IntTreeNode(middle); 
      root.left = createBST(array, left, middle - 1); 
      root.right = createBST(array, middle + 1, right); 
      return root; 
     } else { 
      return null; 
     } 
    } 

Я проверил этот код против автора, и это почти идентичны.
Однако мне сложно анализировать временную сложность этого алгоритма.
Я знаю, что это не будет работать в O (logn) как Binary Search, потому что вы не выполняете столько же работы на каждом уровне рекурсии. E.G на первом уровне, 1 единица работы, 2-й уровень - 2 единицы работы, 3-й уровень - 4 единицы работы, вплоть до регистрации (n) уровень - n единиц работы.

Так основаны от того, количество шагов, этот алгоритм требует будет ограничена сверху этим математическим выражением

, который после просмотра Infinite geometric series, я оценил в

или 2n, которые будет в O (n)

Вы согласны с моим работа здесь и что этот алгоритм будет работать в O (n) или я что-то пропустил или он действительно работает в O (nlogn) или какой-либо другой класс функций?

Answer 1

Иногда вы можете упростить расчеты, вычислив количество времени на элемент в результате, а не рекурсивные отношения. Этот трюк применяется здесь. Начните с изменения кода в этом, очевидно, эквивалентной форме:

private static IntTreeNode createBST(int[] array, int left, int right) { 
    int middle = array[(left + right)/2; 
    IntTreeNode root = new IntTreeNode(middle); 
    if (middle - 1 >= left) { 
     root.left = createBST(array, left, middle - 1); 
    } 
    if (right >= middle + 1) { 
     root.right = createBST(array, middle + 1, right); 
    } 
    return root; 
} 

Теперь каждый вызов createBST непосредственно создает 1 узел. Поскольку в конечном дереве есть n узлов, должно быть n общее количество звонков на createBST, и поскольку каждый вызов напрямую выполняет постоянный объем работы, общая временная сложность O (n).

Answer 2

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