Пространственная сложность обхода порядка обхода уровней с использованием очереди

Это код обхода порядка уровней:

public void bfsTraveral() {
    if (root == null) {
        throw new NullPointerException("The root cannot be null.");
    }
    int currentLevelNodes = 0;
    int nextLevelNodes = 0;

    final Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.add(root);
    currentLevelNodes++;

    while(!queue.isEmpty()) {
        final TreeNode node = queue.poll();
        System.out.print(node.element + ",");
        currentLevelNodes--;
        if (node.left != null) { queue.add(node.left); nextLevelNodes++;}
        if (node.right != null) { queue.add(node.right); nextLevelNodes++;}
        if (currentLevelNodes == 0) {
            currentLevelNodes = nextLevelNodes;
            nextLevelNodes = 0;
            System.out.println();
        }
    }

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

Спасибо,


java data-structures big-o binary-tree space-complexity
person JavaDeveloper    schedule 14.07.2013    source источник
comment
Что такое h? Что такое n?   -  person Oliver Charlesworth    schedule 14.07.2013
comment
возможный дубликат Временная сложность обхода порядка уровней   -  person Andy    schedule 14.07.2013

Ответы (2)


arrow_upward
9
arrow_downward

Если подумать, в дереве с n узлами невозможно одновременно поставить в очередь более n узлов, поскольку ни один узел не будет поставлен в очередь дважды. Это дает непосредственную верхнюю границу O (n). Однако это не жесткая граница, поскольку, если дерево представляет собой вырожденный связанный список, тогда использование памяти будет просто O (1).

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

Следовательно, ваша оценка верна, но оценка O(n) намного лучше.

Надеюсь это поможет!

person templatetypedef    schedule 01.11.2013

arrow_upward
3
arrow_downward

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

Путаница между O2^h и O(n) заключается в том, что не упоминается, является ли сложность пространства для наихудшего случая или наилучшего случая, потому что h отличается для наихудшего и наилучшего случая. -case и может ввести в заблуждение в случае Best-case.

Наихудший случай (когда дерево сбалансировано): O(n)

Когда дерево сбалансировано, последний уровень будет иметь максимальное количество узлов, и это будет 2^h. А для сбалансированного дерева h будет log n. Итак, O(2^h) => O(2 ^ (log n)) => O(n)

Оптимальный случай (когда дерево представляет собой вырожденный связанный список): O(1)

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

person Yatendra    schedule 10.10.2018