我有一个树遍历算法，它通常在O（bm）中运行，其中b是分支因子，m是最大深度 .
使用迭代加深，该算法一次又一次地运行，在增加的深度m次：
O（bm）=b⁰b¹b²... bm
基于我对时间复杂度的有限理解，我们采用最大元素，因为随着时间的推移，这是最重要的元素，因此元素将是bm，其中m是达到的最大深度 .
因此，根据这些知识，我会得出结论，迭代加深算法也在O（bm）中运行 .
但是，从逻辑的角度来看，我无法理解树遍历可能具有完全相同的时间复杂度，无论算法在深度m处运行一次，还是在深度m处运行m次 .
bm固有地小于Σk= 0，..，mbk . 因此迭代加深的时间复杂性不应该更高吗？
或者有什么我不明白的东西？
2 回答
基本上你要问为什么以下两个函数在大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
似乎f1随着n的增长而做更多的工作，所以说两者都是O（n）并不“公平” . 但它们的时间复杂度受线性函数的限制：对于某些（大）常数c，我可以说两个函数的运行时间将低于f（n）= cn，因此整个时间复杂度为O（n） .
“完全相同”的时间复杂度与“花费精确时间”不同 . 说“完全相同的时间复杂性”就像是说“以相同的速度增长，达到恒定因子”，这是一个粗略的估计 .
例如，如果
b = 3，则您要比较这两个数字序列：让我们表示第一个数字
D(m)（对于"DFS"），第二个数字I(m)（对于"iterative deepening"），然后当然，I（m）大于D（m），但它们具有相同的增长率 . 这个想法用
I(m) = O(D(m))表示 .数学上，
I(m) = O(D(m))，因为存在这样一个常数k，I(m) < k * D(m)为所有m;这里k = 3/2.