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

Итак, я знаю, что пространственная сложность рекурсивного обхода по порядку составляет 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).

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


data-structures traversal binary-tree inorder
person NotSure    schedule 17.12.2016    source источник
comment
Вы не просто толкаете — вы хлопаете. Таким образом, определенные части стека используются более одного раза. Высота дерева определяет, насколько сильно вы нажимаете, прежде чем сможете выпрыгнуть. Кстати -- я думаю, что у вас опечатка, не должна ли функция вызывать себя, а не preorderPrint?   -  person John Coleman    schedule 17.12.2016
comment
Смотрите это для более четких ответов: " title="как вы находите пространственную сложность рекурсивных функций, таких как эта"> stackoverflow.com/questions/33590205/   -  person Abhijeet Khangarot    schedule 19.11.2019

Ответы (3)


arrow_upward
23
arrow_downward

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

person Stefan Haustein    schedule 17.12.2016

arrow_upward
5
arrow_downward

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

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

  1
 / \
    2
   / \
      3

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

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

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

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

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

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

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

person RBT    schedule 29.12.2017
comment
Это определенно зависит от характеристик вашего бинарного дерева. В общем случае да, в худшем случае будет O(N) для несбалансированного дерева. Но если вы точно знаете, что ваше дерево сбалансировано (например, AVL или красно-черное), то вам гарантируется, что высота вашего дерева будет не более Log(N), и поэтому сложность вашего пространства будет O(log N) для обхода. - person Eric Cornelson; 18.11.2018

arrow_upward
0
arrow_downward

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

person Abhijeet Khangarot    schedule 19.11.2019