一个依赖收敛的算法的大O
Big O of an algorithm that relies on convergence
我想知道是否可以使用大 O 表示法来表达依赖于收敛的算法的时间复杂度。
在我见过的大多数算法分析中，我们根据输入大小评估函数的增长率。
对于具有某些收敛标准的算法（我们重复操作直到某个定义的错误度量低于阈值，或者错误度量的变化率低于某个阈值），如何才能我们衡量时间复杂度？收敛和退出该循环所需的迭代次数似乎很难推理，因为算法收敛的方式往往取决于输入的内容，而不仅仅是它的大小。
我们如何用大 O 表示法表示依赖于收敛的算法的时间复杂度？
渐近符号不依赖于收敛。
根据 CLRS 书（算法导论第三版第 3 章第 43 页）：
When we look at input sizes large enough to make only the order of
growth of the running time relevant, we are studying the
asymptotic efficiency of algorithms.That is, we are concerned with how the running time of an algorithm increases with he size of
the input in the limit, as the size of the input increases without
bound. Usually, an algorithm that is asymptotically more efficient
will be the best choice for all but very small inputs.
你提到你的代码（或想法）有无限循环并继续满足条件并且你命名为满足条件收敛但在这个意义上，收敛与渐近无关像 big O 这样的符号，因为它必须完成，因为代码成为算法的必要条件是它的迭代必须完成。您需要确保代码的迭代完成，这样您才能告诉它算法并对其进行渐近分析。
另一件事是，有时一个结果的 运行 时间更长，而另一个结果的 运行 时间更少。这与渐近分析无关。这是最好的情况，最坏的情况。我们可以通过 big 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 是迭代次数。
就迭代次数而言，这可以是 re-written，如下所示：iterations = log(1 / E)，其中 E 是所需的误差值。
因此，如果我们有一个算法在收敛循环的每次迭代中执行一些线性运算（如上例所示），我们可以推测我们的时间复杂度为 O(N * log(1 / E) ).除了输入大小之外，我们函数的增长率还取决于我们愿意容忍的错误量。
因此，如果我们能够确定一些 属性 关于收敛行为的信息，例如它是否是误差的函数或输入的大小，那么我们就可以执行渐近分析。
以PageRank为例，其计算中使用了一种名为power iteration的算法，该算法近似于矩阵的主要特征向量。似乎可以将收敛速度显示为前两个特征值的函数（如 link 所示）。
从数学的角度来看，主要问题是 Rate of convergence of used approach. I am not so familiar with numerical methods for speak fluently about higher than 1 Dimensions (matrixes and tensors you probably more interested in). But ley's take other example of Equation Solving 比二分法的估计，上面已经估计为 O(log(1/e))。
考虑 Newton method 并假设我们尝试为所有浮点数找到一个精度为 e=10e-8 的根。我们有平方作为收敛率，所以我们有大约 2*log(float_range/e) 循环迭代，这意味着与二分法算法复杂度相同 O(log(range/accuracy))，如果我们能够计算恒定时间的导数.
希望这个例子对您有所帮助。
我想知道是否可以使用大 O 表示法来表达依赖于收敛的算法的时间复杂度。
在我见过的大多数算法分析中，我们根据输入大小评估函数的增长率。
对于具有某些收敛标准的算法（我们重复操作直到某个定义的错误度量低于阈值，或者错误度量的变化率低于某个阈值），如何才能我们衡量时间复杂度？收敛和退出该循环所需的迭代次数似乎很难推理，因为算法收敛的方式往往取决于输入的内容，而不仅仅是它的大小。
我们如何用大 O 表示法表示依赖于收敛的算法的时间复杂度？
渐近符号不依赖于收敛。
根据 CLRS 书（算法导论第三版第 3 章第 43 页）：
When we look at input sizes large enough to make only the order of growth of the running time relevant, we are studying the asymptotic efficiency of algorithms.That is, we are concerned with how the running time of an algorithm increases with he size of the input in the limit, as the size of the input increases without bound. Usually, an algorithm that is asymptotically more efficient will be the best choice for all but very small inputs.
你提到你的代码（或想法）有无限循环并继续满足条件并且你命名为满足条件收敛但在这个意义上，收敛与渐近无关像 big O 这样的符号，因为它必须完成，因为代码成为算法的必要条件是它的迭代必须完成。您需要确保代码的迭代完成，这样您才能告诉它算法并对其进行渐近分析。
另一件事是，有时一个结果的 运行 时间更长，而另一个结果的 运行 时间更少。这与渐近分析无关。这是最好的情况，最坏的情况。我们可以通过 big 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 是迭代次数。
就迭代次数而言，这可以是 re-written，如下所示：iterations = log(1 / E)，其中 E 是所需的误差值。
因此，如果我们有一个算法在收敛循环的每次迭代中执行一些线性运算（如上例所示），我们可以推测我们的时间复杂度为 O(N * log(1 / E) ).除了输入大小之外，我们函数的增长率还取决于我们愿意容忍的错误量。
因此，如果我们能够确定一些 属性 关于收敛行为的信息，例如它是否是误差的函数或输入的大小，那么我们就可以执行渐近分析。
以PageRank为例，其计算中使用了一种名为power iteration的算法，该算法近似于矩阵的主要特征向量。似乎可以将收敛速度显示为前两个特征值的函数（如 link 所示）。
从数学的角度来看，主要问题是 Rate of convergence of used approach. I am not so familiar with numerical methods for speak fluently about higher than 1 Dimensions (matrixes and tensors you probably more interested in). But ley's take other example of Equation Solving 比二分法的估计，上面已经估计为 O(log(1/e))。
考虑 Newton method 并假设我们尝试为所有浮点数找到一个精度为 e=10e-8 的根。我们有平方作为收敛率，所以我们有大约 2*log(float_range/e) 循环迭代，这意味着与二分法算法复杂度相同 O(log(range/accuracy))，如果我们能够计算恒定时间的导数.
希望这个例子对您有所帮助。