依赖于收敛的算法的大O

为了分析依赖于收敛的算法,似乎我们必须证明一些关于收敛速度的东西。

收敛通常有一个终止条件,用于检查我们的误差度量是否低于某个阈值:

do {
  // some operation with time complexity O(N)
} while (errorMetric > 0.01) // if this is false, we've reached convergence

通常,我们试图定义算法的收敛方式,通常是通过确定它是某个函数。

例如,我们可以证明算法的误差度量是迭代次数的函数,因此误差=1/2^i,其中i是迭代次数。

这可以根据迭代次数重新编写,如:迭代次数=log(1/E),其中E是所需的错误值。

因此,如果我们有一个在收敛循环的每次迭代上执行一些线性操作的算法(如上例所示),我们可以推测我们的时间复杂度为O(N*log(1/E))。我们函数的增长率取决于我们愿意容忍的错误量,以及输入大小。

所以,如果我们能够确定关于收敛行为的一些性质,比如它是误差的函数,或者输入的大小,那么我们可以进行渐近分析。

以PageRank为例,它是一种称为 power iteration 在其计算中使用,这是一种近似矩阵主特征向量的算法。收敛速度似乎可能是前两个特征值的函数(如链接所示)。

渐近符号不依赖于收敛。

根据 CLRS 本书(算法导论第三版第3章第43页):

当我们看到输入大小足够大,只需要 与运行时间的增长相关,我们正在研究 渐近的 算法的效率。也就是说,我们关心的是算法的运行时间如何随着 中的输入 限度 ,随着输入大小的增加 跳跃通常,一种渐近更有效的算法 将是除非常小的输入之外的所有输入的最佳选择。

您提到您的代码(或想法)具有不定式循环并继续满足条件,您将其命名为满足条件 汇聚 但在这个意义上,收敛与渐近符号无关,如 big O ,因为它必须完成,因为代码成为算法的一个必要条件是它的迭代必须完成。您需要确保代码的迭代完成,以便告诉它算法,并对其进行渐近分析。

另一件事是真的,也许有时一个结果有更多的运行时间,但另一个结果有更少的运行时间。这与渐近分析无关。它是 最好的情况,最坏的情况 . 我们可以通过 大O 或其他渐近符号。其中最可靠的是在最坏的情况下分析算法。最后,为了分析代码,您应该准确描述算法的步骤。

从数学的角度来看,主要问题是 Rate of convergence 使用的方法。我不太熟悉数值方法,不能流利地谈论高于1维的问题(你可能更感兴趣的矩阵和张量)。但ley的另一个例子是 Equation Solving 比二等分,已在上面估计为 O(log(1/e)) 。

考虑 Newton method 假设我们试图找到一个精度为e=10e-8的所有浮点数的根。我们有平方作为收敛速度,所以我们有大约2*log(float\u range/e)循环迭代,这意味着与二分法算法的复杂性相同 O(log(range/accuracy)) ,如果我们能够计算常数时间的导数。

希望这个例子对你有意义。