我理解极小化极大算法和Alpha-Beta剪枝的基础知识。在所有文献中，他们提到最佳情况下的时间复杂度是O(b^(d/2))，其中b是分支因子，d是树的深度，而基本情况是当所有优先节点首先被扩展时。

在我的“最佳情况”示例中，我有一个4层的二叉树，因此在16个终端节点中，我最多需要扩展7个节点。这与O(b^(d/2))有什么关系？

我不明白他们是如何得出O(b^(d/2))的。

回答：

O(b^(d/2))对应于Alpha-Beta剪枝的最佳情况时间复杂度。解释如下：

在分支因子为b且搜索深度为d层的情况下，当移动顺序最差时，评估的叶节点位置的最大数量是O(b*b*…*b) = O(b^d) – 这与简单的极小化极大搜索相同。如果搜索的移动顺序是最优的（意味着总是先搜索最佳移动），则评估的叶节点位置数量大约为O(b*1*b*1*…*b)（对于奇数深度）和O(b*1*b*1*…*1)（对于偶数深度），或O(b^(d/2))。在后一种情况下，当搜索的层数为偶数时，有效分支因子减少到其平方根，或者等效地，搜索可以用相同数量的计算深入两倍。在b*1*b*1*…的解释中，必须研究所有第一玩家的移动以找到最佳的，但对于每个移动，只需要最佳的第二玩家移动来反驳除第一个（也是最佳的）第一玩家移动之外的所有移动 – Alpha-Beta确保不需要考虑其他第二玩家的移动。

简单来说，你每隔两层“跳过”一次：

O描述了一个函数在参数趋向于特定值或无穷大时的极限行为，因此在你的情况下，将O(b^(d/2))与b和d的小值精确比较并没有实际意义。