我有一个树遍历算法，它通常在 O(b m ) 中运行，其中 b 是分支因子，m 是最大深度。
使用迭代深化，这个算法一遍又一遍地运行，m 次以增加深度：
O(b m ) = b⁰ + b¹ + b² + ... + b m
基于我对时间复杂度的有限理解，我们采用最大元素，因为随着时间的推移，它是最重要的元素，因此该元素将是 b m，其中 m 是达到的最大深度。
因此，有了这些知识，我会得出结论，迭代深化算法也在 O(b m ) 中运行。
但是我很难理解，从逻辑的角度来看，无论算法是在深度 m 处运行一次，还是在深度 m 处运行一次，树遍历如何具有完全相同的时间复杂度。
b m本质上小于 Σ k=0,..,m b k。因此迭代加深的时间复杂度不应该更高吗？
还是有什么我不明白的地方？
基本上你在问为什么以下两个函数在大 O 方面具有相同的时间复杂度（因为它们都是 O(n^m)）：
原因是，在某些时候，对于 n 和 m 的值，项 n^m 使这些函数的所有其他项相形见绌。随着输入的增长，整个函数的运行时间将由 n^m 决定。
即使你想出一个需要 n^m + 1000000000000 的函数，那么在某些时候 n^m 仍然是运行时间的决定性术语。换句话说，这两个函数的运行时间都受一个函数的限制，该函数的项为 n^m 乘以某个常数。
在您的示例中，在深度 m 处运行一次树遍历或运行它 m 次直到深度 m 具有相同的时间复杂度，因为随着树的增长，在深度 m 处运行的运行时间使所有其他运行相形见绌。查看在深度 m 处运行需要多长时间基本上是找到一个限制两个任务运行时的函数所需的全部内容。
再举一个例子，我们可以考虑两个 O(n) 的函数：
随着 n 的增长，f1 似乎做了更多的工作，所以说两者都是 O(n) 是不“公平的”。但是它们的时间复杂度受线性函数的限制：对于一些（大）常数 c，我可以说两个函数的运行时间都将低于 f(n) = cn，因此整个时间复杂度为 O(n)。
“完全相同”的时间复杂度与“采取确切的时间”不同。说“精确相同的时间复杂度”就像说“以相同的速度增长，直到一个常数因子”，这是一个粗略的估计。
例如，如果b = 3，您正在比较这两个数字序列：
3^m, or (1, 3, 9, 27, 81, ...)
3^0+3^1+...+3^m, or (1, 4, 13, 40, 121, ...)
让我们表示第一个数字D(m)（用于“DFS”）和第二个数字I(m)（用于“迭代深化”），然后
I(m) = 3/2 * D(m) - 1/2
I(m) 确实大于 D(m)，但它们具有相同的增长“顺序”。这个想法用 表示I(m) = O(D(m))。
在数学上，I(m) = O(D(m))，因为存在这样一个常数k，I(m) < k * D(m)对于所有m; 在这里k = 3/2。