我不确定这个问题是否应该放在 stackoverflow 或 cs.stackexchange.com 上，所以如果我应该移动它，请告诉我。
我试图找到蒙特卡洛树搜索（MCTS）的时间复杂度。谷歌搜索没有帮助，所以我想看看我自己计算了多远。
它为n迭代或在时间用完之前执行四个步骤。所以我们会有
O(n*(选择+扩展+模拟+反向传播))
扩展只是将一个子节点添加到当前选定的节点。假设您没有使用单链表或类似的东西来存储树的孩子，这可能会在恒定时间内发生，所以我们可以排除它：
O(n*(选择+模拟+反向传播))
给定分支因子b和t树中的节点总数，我假设选择阶段在 O(b*log b t) 中运行，因为树的深度是 log b t，并且在每个深度，我们去超过b个孩子。
所以我们的时间复杂度变成
O(n*(b*log b t+模拟+反向传播))
反向传播所花费的时间也与树的深度成正比，因此变为：
O(n*(b*log b t+模拟+b*log b t))
但现在我不确定如何将模拟阶段添加到此。