我们如何确定minmax的时间和空间复杂度？

Question

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

Answer 1

时间

树中的所有节点都必须在某个时刻生成一次，并且假设生成一个节点需要花费常数时间c（常数时间可以变化，您可以只选择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)。

Answer 2

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

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

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

我将大胆地假设您正在谈论 IDDFS。 O(b^d) 和 O(bd) 从何而来的解释在 中得到了很好的解释这篇维基文章。