javascript - 这个算法的时间和空间复杂度是O(n)还是O(1)？

Question

Update: - Wikipedia says o(n) not O(n) so this algorithm isn't an in-place solution. - Debating whether this solution runs in O(n) or O(1).

这是我对 LeetCode 问题 Flatten Binary Tree to Linked List 的解决方案。在时间和空间复杂度分析方面，根据一些解释，我不太确定它是O(1)。我认为由于堆栈的使用，它的时间复杂度为O(n)。我的分析正确吗？

根据Wikipedia ，O(n) 仍被接受为就地。

More broadly, in-place means that the algorithm does not use extra space for manipulating the input but may require a small though nonconstant extra space for its operation. Usually, this space is O(log n), though sometimes anything in o(n) is allowed.

/**
 * Function flattens a binary tree.
 * Time = O(n) because we iterate through all nodes.
 * Space = O(n) because we use a stack.
 * @param {root} root Input tree.
 */
var flatten = function(root) {
    // If reach end of leaf node, return.
    if (root === null) return;

    let stack = [];
    let currentNode = root;

    while (true) {
        // Push right branch to stack first,
        if (currentNode.right) stack.push(currentNode.right);
        // then left branch.
        if (currentNode.left) stack.push(currentNode.left);
        // If there are branches in stack:
        if (stack.length > 0) {
            // Change the current currentNode right branch to the last element of the stack:
            currentNode.right = stack.pop();
            // Change left branch to null
            currentNode.left = null;
            // Advance by changing current currentNode to the right currentNode.
            currentNode = currentNode.right;
        }
        else break;
    }
}

Answer 1

是的，该算法使用 Theta(N) 最坏情况时间和最坏情况附加空间，其中 N 是树中的节点数。时间复杂度很明显，因为您将每个节点推送和弹出一次。

空间复杂度有点棘手，但例如考虑一棵树，它是一个列表，其中列表的下一个元素是左子元素，但假设它对于每个列表节点都有一个右子元素，该右子元素本身没有 child 。

在该示例中，您的算法将遍历左侧节点，将右侧节点添加到堆栈中，但仅在到达原始列表末尾时才弹出这些节点，即大约有 N/2 堆栈中的元素。

最好情况下，时间复杂度仍然是 Theta(N)，因为您总是迭代所有节点，但最好情况下空间复杂度是 Theta(1) >，因为例如已经是列表的树永远不会将堆栈大小增加到超过 1。

这通常不会被视为就地算法，因为它使用额外的Theta(N)空间，至少在最坏的情况下是这样。正如维基百科文章中所解释的，就地算法应该需要o(N)额外空间，或者我想说，通常只需要O(1) 或稍多一点，例如O((ln N)^k) 对于某个 k 最大值。应该计算最坏情况还是平均情况是另一个问题。

o(N) 是little-o 表示法，而不是big-O 表示法。这意味着对于每个 c > 0，时间/空间都渐近小于c*N。因此，Theta(N) 永远不会 o(N)。

此外，Theta(N) 意味着它不仅是 O(N)，也意味着对于 c*N 渐近小于 c*N em>some c > 0，而且对于某些 c 来说，它渐近大于 c*N。

如果您想要更严格定义的就地算法，则不应需要任何额外的动态大小容器。