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

Question

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

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). Это звучит неправильно для меня. Пожалуйста, поделитесь своим мнением.

Спасибо,

Answer 1

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

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

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

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

Answer 2

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

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

---

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

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

Best-Case (когда дерево является вырожденным связанным списком): O(1)

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