algorithm - 一个依赖收敛的算法的大O

Question

我想知道是否可以使用大 O 表示法来表达依赖于收敛的算法的时间复杂度。

在我见过的大多数算法分析中，我们根据输入大小评估函数的增长率。

如果算法有一些收敛标准(我们重复一个操作，直到某个定义的误差指标低于阈值，或者误差指标的变化率低于某个阈值)，我们如何衡量时间复杂度？收敛和退出该循环所需的迭代次数似乎很难推断，因为算法收敛的方式往往取决于输入的内容，而不仅仅是输入的大小。

我们如何用大 O 表示法表示依赖于收敛的算法的时间复杂度？

Answer 1

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

收敛通常有一个终止条件来检查我们的错误指标是否低于某个阈值:

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

一般来说，我们试图定义一些关于算法收敛方式的东西——通常是通过确定它是某物的函数。

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

这可以根据迭代次数重写为:iterations = log(1/E)，其中 E 是所需的误差值。

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

因此，如果我们能够确定关于收敛行为的一些属性，例如它是否是误差的函数或输入的大小，那么我们就可以执行渐近分析。

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