logo标签列表

理解大O符号——破解编程面试第9例

algorithmtreebig-onotation
4

I got stuck with this two codes.

Code 1

int f(int n){
    if (n <= 1){
         return 1;
    }
    return f(n-1) + f(n-1);
}

代码 2（平衡二叉搜索树）

int sum(Node node){
    if(node == null){
        return 0;
    }
    return sum(node.left) + node.value + sum(node.right);
}

作者称 Code 1 的运行时复杂度为 O(2^n)，空间复杂度为 O(n)。

而 Code 2 的时间复杂度为 O(N)。

我不知道这两段代码有什么不同。它们看起来都是相同的二叉树。

7个回答
6

首先，第一个片段的时间复杂度是O(2^n)，而不是O(n^2)。

原因是：每一步我们都会减少n，但是创建的调用次数是两倍，所以对于n，我们将使用f(n-1)两次进行调用，对于n-1的每个调用，我们将使用f(n-2)两次进行调用 - 这是4个调用，如果我们再往下走一层，我们将使用f(n-3) 8次进行调用：因此调用次数为：2^1、2^2、2^3、2^4、...、2^n。

第二个片段在二叉树上执行一次遍历，并且恰好到达每个节点，因此它的时间复杂度是O(n)。

那么完美二叉树的时间复杂度是O(2^n)吗？因为我认为它与第一个具有相同的结构。 - Daniel
3
第一个与树无关。第二个是二叉树，但不一定平衡。当我们说它的时间复杂度为O(n)时，考虑的是树中节点的数量n。 - Nir Alfasi
6

首先，重要的是要理解在两种情况下N的含义。在第一个示例中，因为您直接在代码中看到它，所以很明显。对于您的第一种情况，如果您构建f(i)调用的树形结构，您会发现它包含O(2^N)个元素。确实，

            f(N)             // 1 node
        /          \ 
   f(N-1)         f(N-1)     // 2 nodes
  /      \      /      \
f(N-2) f(N-2)  f(N-2) f(N-2) // 2^2 nodes
...
f(1) ........ f(1)           // 2^(N-1) nodes

在第二种情况下，N（很可能）是树中元素的数量。从代码中可以看出，我们恰好遍历每个元素 - 您可以意识到这一点，因为您看到每个树节点都会调用node.value一次。因此时间复杂度为O(N)。
请注意，在这样的任务中，N通常表示输入的大小，而输入是什么取决于您的问题。它可以只是一个数字（就像您的第一个问题），一个一维数组，一个二叉树（就像您的第二个问题），甚至是矩阵（尽管在后一种情况下，您可能会看到明确的语句，如“大小为M * N的矩阵”）。
因此，您的困惑可能来自于两个问题之间“N的定义”不同的事实。换句话说，我可能会说n2 = 2^n1。
2
点赞明确指出OP问题的根源：N的定义差异。 - meowgoesthedog
我觉得混淆的主要原因是OP认为第一段代码也代表了一个二叉树。 - Nir Alfasi
我有一种感觉（对于第一个例子），这仍然是N的另一种定义。书中将N称为树的深度，而不是输入值。因此，对于f(4)，树的深度为N=3（而不是4）。节点数（或调用次数）为2^(depth+1) - 1。也就是2^4 - 1 = 15。尽管如此，我承认对解释有些困惑。 - Kurt Bourbaki
1
第一段代码确实是O(2^n)。
但是第二段代码不能是O(n)，因为那里没有n。这是许多人忘记的事情，通常他们会假设n是什么，而不澄清它。
实际上，你可以根据任何东西估计任何东西的增长速度。有时它是输入的大小（在第一个代码中，取决于大数的使用，O(1)或O(log n)），有时只是数字参数。
因此，当我们开始思考第二个代码中的时间和内存依赖关系时，我们可以得到以下内容：
  1. 时间=O(树中节点数)
  2. 时间=O(2^树的高度)
  3. 额外空间=O(树的高度)
  4. 额外空间=O(log(节点数))（如果树是平衡的）
所有这些都是正确的 - 它们只是将某些东西与不同的事物联系起来。
2
“他们假设n是什么，却没有澄清。” - 你说得对，我们不应该假设任何东西，但是在第二种情况中，n表示“树中节点的数量”，这是非常微不足道的，因此有时会被忽略或故意不提及以减少冗余。;) - Nir Alfasi
1

您可能会对两种情况中的“N”感到困惑。在第一种情况下，N指的是输入给定的值。例如，如果N=4，则调用函数的次数为2^4=16。您可以绘制递归图来说明。因此，复杂度为O(2^N)。

在第二种情况下，N指的是二叉树中节点的数量。因此，这个N与输入无关，而是二叉树中已经存在的节点数量。因此，当用户调用函数时，它会恰好访问每个节点一次。因此，复杂度为O(N)。

如果N=4，则被调用的函数数量为2^4=16。这似乎不正确。如果N=4，则f()函数被调用15次。您可以绘制树形图来可视化它。 - Kurt Bourbaki
0

代码1：

if()语句根据传入的参数运行n次，但函数调用本身只运行n-1次。简化公式如下：

n * (n-1) = n^2 - n = O(n^2 - n) = O(n^2)

代码2：

搜索只遍历了树的每个元素一次，函数本身没有任何for()循环。由于有n个项目且它们仅被访问一次，因此时间复杂度为O(n)。

0

对于代码2，要确定一个函数的大O，我们不仅需要考虑递归的成本，还需要考虑递归运行的次数吗？

如果我们使用两种方法来估计使用递归树和主定理的大O：

递归树： 每个级别中的总成本将是cn，因为递归调用的数量和输入的分数相等，并且树的级别是lg（n），因为它是平衡二叉搜索树。所以运行时间应该是nlg（n）？

主定理： 这应该是第2种情况，因为f（n）= n^logbase a（b）。因此根据主定理，它应该是nlg（n）的运行时间？

0

我们可以将其视为O(2^Depth)。

在第一个例子中：深度是N，这恰好是书中提到的问题的输入。

在第二个例子中：它是一棵平衡的二叉搜索树，因此它有Log(N)层（深度）。注意：N是树中元素的数量。

=> 让我们应用我们的O(2^Depth).. O(2^(Log(N)) = O(N)，留下O(N)的复杂度。

提醒：

  • 在计算机科学中，我们通常将Log2(n)称为Log(n)。
  • 以b为底数，x的对数是你放在b上得到x的指数。

在上述复杂度中：O(2^(Log(N)，我们将底数2提高到Log2(N)，得到N。（检查两个提醒）

这个link可能会有用。

深度为N，这恰好是书中提到的问题的输入。你确定吗？树的深度是从根节点到最远叶节点的边数。因此，对于书中表示的树，深度应该是3（而不是4）。你同意吗？ - Kurt Bourbaki
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接