Почему сложность пространства рекурсивного обхода обхода O(h), а не O(n)

Question

Итак, я знаю, что пространственная сложность рекурсивного обхода порядка равна O(h), а не O(n), так как h = высота дерева и n = количество узлов в дереве.

Это почему? Допустим, это код для обхода:

public void inorderPrint (TreeNode root) {

    if (root == null) {
        return;
    }

    inorderPrint(root.left);
    System.out.println(root.data);
    inorderPrint(root.right);

}

Мы помещаем n адресов памяти в стек вызовов, поэтому сложность пространства должна быть O(n).

Что мне не хватает?

Answer 1

Адреса удаляются из стека при возврате. Это пространство используется повторно при совершении нового вызова с уровня ближе к корню. Таким образом, максимальное количество адресов памяти в стеке одновременно является высотой дерева.

Answer 2

ИМХО, вы должны рассматривать сложность пространства как O(n) вместо. Имея дело со сложностями пространства и времени в нотации Big O, мы всегда стараемся дать значение сложности как функцию количества входных элементов, которое n в этом случае.

Кроме того, если вы рассмотрите случаи двоичного дерева с перекосом вправо или двоичного файла с перекосом влево, вы найдете это O(n) Пространственная сложность как подходящая. Посмотрите на приведенные ниже случаи правильного перекошенного двоичного дерева:

  1
 / \
    2
   / \
      3

Количество узлов, n = 3

Количество кадров стека, необходимых для рекурсивного обхода = 3

  1
 / \
    2
   / \
      3
     / \
        4
       / \

Количество узлов, n = 4

Количество кадров стека, необходимых для рекурсивного обхода = 4

Таким образом, вы можете сделать вывод, что O(n) является подходящей пространственной сложностью в таком худшем случае относительно древовидной структуры. Во всех других случаях / типах деревьев количество требуемых кадров стека всегда будет меньше n, И именно так мы выражаем сложности. Фактическое пространство, занимаемое всеми возможными случаями, всегда должно быть меньше или равно изображенной функции.

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

Answer 3

Сложность рекурсии в пространстве всегда равна высоте / глубине рекурсии, поэтому, следуя этому общему правилу, при обходе по порядку может быть не более h высоты, где h - длина самого глубокого узла от корня. Пространственная сложность рекурсии = O(глубина дерева рекурсии).