5

我在确定空间和时间复杂性时遇到了一些麻烦。例如，如果我有一棵树，它有一个分支因子b并且最多有一个深度d，我如何计算时间和空间复杂度？我知道它们是 O(b^d) 和 O(bd)，但我的问题是如何获得这些值。

4

2 回答 2

8

时间

树中的所有节点都必须在某个时间点生成一次，并且假设c生成一个节点需要一个常数时间（常数时间可能会有所不同，您可以选择c生成任何节点的最高常数时间） . 顺序由算法确定，并确保节点不必重复扩展。

nodes          b=2                        b=3
b^0             *                          *
              /   \               /        |        \
b^1          *     *             *         *         *
            / \   / \         /  |  \   /  |  \   /  |  \
b^2        *   * *   *       *   *   * *   *   * *   *   * 
               ...                        ...

正如您在图中看到的那样，c*b^0精确计算第一级需要成本c。树中的下一层将包含一个节点，生成第二层b^1需要花费。c*b^1 = c*b对于第三级b，第二级中的每个节点都会再次有节点，这意味着b*b^1 = b^2$节点和成本为c*b^2.

在深度树的最深层次d将有b^d节点，该层次的工作是c*b^d。至此所做的工作总量为c*b^0 + c*b^1 + ... + c*b^d。对于复杂性，我们只查看上升最快的项并丢弃常数，因此我们得到：

O(c + c*b + ... + c*b^d) = O(c*b^d) = O(b^d).

本质上：时间是一个函数f(d) = SUM(i=1..d){c*b^i}，和O(f(d)) = O(b^d)。

空间

该图显示了不同阶段的算法b=3。*表示当前展开的节点，?表示未知节点，+表示已完全计算分数的节点。

                    branching factor b = 3                     space
         *             *             *             *             b
       / | \         / | \         / | \         / | \         
      *  ?  ?       *  ?  ?       +  *  ?       +  +  *          b
    / | \         / | \            / | \            / | \      
   *  ?  ?       +  +  *          +  *  ?          +  +  *       b
 / | \               / | \         / | \               / | \   
*  ?  ?             +  *  ?       +  *  ?             +  +  *    b

为了计算节点的分数，您展开节点，选择一个子节点并递归展开，直到到达深度处的叶节点d。完全计算完一个子节点后，您将转到下一个子节点。计算完所有b子节点后，将根据子节点计算父节点分数，此时可以从存储中删除子节点。上图说明了这一点，其中算法显示在 4 个不同的阶段。

在任何时候，您都扩展了一条路径，并且您需要c*b存储来存储每个级别的所有子节点。这里再次假设每个节点需要恒定数量的空间。关键是任何子树都可以通过它的根来概括。由于路径的最大长度为d，因此您将最大程度地需要c*b*d空间。如上所述，我们可以去掉常数项，我们得到O(c*b*d) = O(b*d)。

于 2012-02-26T00:52:51.187 回答
4

空间复杂度相当于“我需要为此算法分配多少内存”。时间复杂度相当于“执行需要多长时间（抽象意义上的”）。

具有分支因子 b 和深度 d 的树将在其第零级有一个节点，在其第一级有 b 个节点，在其第二级有 b*b = b^2 个节点，在其第三级有 b^2 * b = b^3级别等。在这四个级别（深度 3）中，它有 1 + b + b^2 + b^3。就复杂性而言，我们只保留最高阶项，通常会丢弃任何乘法常数。因此，对于空间复杂度，您最终会得到 O(b^d) 的复杂度。

现在在时间复杂度中，您计算​​的不是节点数，而是您的算法将完成的循环或递归调用的数量（最坏情况）。

我要冒昧地假设你在谈论 IDDFS。这篇wiki 文章很好地解释了 O(b^d) 和 O(bd) 的来源。

于 2010-01-17T05:32:29.507 回答