algorithm - 迭代加深如何影响时间复杂度？

Question

我有一个树遍历算法，通常在 O(b^m) 中运行，其中 b 是分支因子，m 是最大深度。

使用迭代加深，这个算法一遍又一遍地运行，m 次，深度增加:

O(b^m) = b⁰ + b¹ + b² + ... + b^m

基于我对时间复杂度的有限理解，我们采用最大的元素，因为随着时间的推移，它是最重要的元素，因此该元素将是 b^m，其中 m 是达到的最大深度.

因此，根据这些知识，我可以得出结论，迭代加深算法也在 O(b^m) 中运行。

但是，从逻辑的角度来看，我很难理解树遍历如何具有完全相同的时间复杂度，无论该算法是在深度 m 运行一次，还是运行 m 次直到深度 m。

b^m 本质上小于 Σ_k=0,..,mb^k。因此，迭代加深的时间复杂度不应该更高吗？

或者有什么我不明白的地方？

Answer 1

基本上您是在问为什么以下两个函数在大 O 方面具有相同的时间复杂度(因为它们都是 O(n^m)):

• n^0 + n^1 + n^2 + ... + n^m
• n^m

原因是，在某些时候，对于 n 和 m 的值，n^m 项使这些函数的所有其他项相形见绌。随着输入的增长，整个函数的运行时间将由 n^m 决定。

即使你想出一个需要 n^m + 1000000000000 的函数，在某个时候 n^m 仍然是决定运行时间的项。换句话说，两个函数的运行时间都受一个函数的限制，该函数的项为 n^m 乘以某个常数。

在您的示例中，在深度 m 运行树遍历一次或运行它 m 次直到深度 m 具有相同的时间复杂度，因为随着树的增长，在深度 m 运行的运行时间使所有其他运行相形见绌。查看在深度 m 运行需要多长时间基本上是找到一个函数来限制两个任务的运行时间所需的全部。

再举个例子，我们可以想到两个都是O(n)的函数:

• f1(n) = 1000000000n + 5
• f2(n) = 3n

似乎随着 n 的增长，f1 做了更多的工作，所以说两者都是 O(n) 是不“公平”的。但是它们的时间复杂度受线性函数的限制:对于某些(大)常量 c，我可以说这两个函数的运行时间将低于 f(n) = cn，因此整个时间复杂度为 O(n)。