时间戳

首页 > 解决方案 > 这个算法的时间和空间复杂度是 O(n) 还是 O(1)？

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

问题描述

更新： - 维基百科说o(n)不是O(n)，所以这个算法不是就地解决方案。- 争论这个解决方案是否在O(n)或O(1).

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

根据Wikipedia，O(n)仍被接受为in-place。

更广泛地说，就地意味着该算法不使用额外空间来操作输入，但可能需要一个很小但非常量的额外空间来进行操作。通常，这个空间是 O(log n)，尽管有时 o(n) 中的任何内容都是允许的。

/**
 * 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;
    }
}

标签： javascriptalgorithmbig-o

解决方案

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

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

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

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

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

o(N)是little-o notation，而不是big-O notation。这意味着时间/空间逐渐小于everyc*N。是因此从不。 c > 0Theta(N)o(N)

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

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

推荐阅读