确定时间和空间的复杂性

Question

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

谢谢!

Answer 1

时间

树中的所有节点必须在某个时刻生成一次,并且假设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。这篇wiki 文章很好地解释了 O(b^d) 和 O(bd) 从何而来。