依赖于收敛的算法的大O.

Question

我想知道是否有可能表达依赖于使用Big O表示法收敛的算法的时间复杂度.

在我看过的大多数算法分析中,我们根据输入大小来评估函数的增长率.

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

我们如何表示依赖于Big 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为例,在其计算中使用称为幂迭代的算法,该算法近似于矩阵的主要特征向量.似乎可以将收敛速率显示为前两个特征值的函数(在链接中示出).