algorithm - 渐近边界和控制结构

Question

到目前为止，在我学习算法的过程中，我一直假设渐近边界与控制结构中的模式直接相关。因此，如果我们有 n^2 时间复杂度，我认为这自动意味着我必须使用嵌套循环。但我发现这并不总是正确的（对于其他时间复杂性，不仅仅是二次的）。如何处理时间复杂度和控制结构之间的这种关系？

谢谢

标签： algorithmtime-complexitycontrol-structure

Answer 1

赖斯定理是对分析运行时间做出一般性陈述的重大障碍。

在实践中，有一系列可以应用的技术。许多算法具有易于分析的嵌套循环结构。当这些循环之一的边界取决于数据时，您可能需要进行摊销分析。分而治之的算法通常可以用 Master Theorem 或 Akra-Bazzi 来分析。

但是，在某些情况下，运行时间分析可能非常微妙。以 union-find 为例：获得逆阿克曼运行时间界限需要证明页面。然后对于像 Collat​​z 猜想这样的事情，我们甚至不知道如何得到一个有限界。