在不使用渐近符号的情况下，繁琐的步数计算是获得算法时间复杂度的唯一方法吗？如果没有每行代码的步数，我们可以得到任何程序的大 O 表示吗？
细节：试图找出几种数值分析算法的复杂性，以决定哪种算法最适合解决特定问题。例如 - 从用于求解 eqns 的 Regula-Falsi 或 Newton-Rhapson 方法中，目的是评估每种方法的确切复杂性，然后决定（输入“n”的值或存在的任何参数）哪种方法不太复杂。
问问题
1809 次
3 回答
5
找出复杂算法的确切复杂性的唯一方法——不是“简单”或困难的方法，而是唯一合理的方法——对其进行分析。算法的现代实现与数值库和 CPU 及其浮点单元有复杂的交互。例如，缓存内内存访问比缓存外内存访问快得多，而且在此之上可能有不止一级缓存。计算步数确实更适合您所说的不足以满足您的目的的渐近复杂性。
但是，如果您确实想自动计算步数，也有办法做到这一点。您可以在每一行代码中添加一个计数器增量命令（如 C 中的“bloof++;”），然后在末尾显示该值。
您还应该了解更精确的时间复杂度表达式 f(n)*(1+o(1))，它对于分析计算也很有用。例如 n^2+2*n+7 简化为 n^2*(1+o(1))。如果常数因子是常用渐近符号 O(f(n)) 困扰您的原因，那么这种改进是一种跟踪它的方法，并且仍然丢弃可忽略不计的项。
于 2010-07-28T04:57:34.847 回答
2
“简单的方法”是模拟它。尝试使用大量 n 值和大量不同数据的算法，绘制结果然后将图表上的曲线与方程匹配。
您的结果可能并不完全正确，它们仅与您生成良好测试数据的能力一样有效，但在大多数情况下，这将起作用。
于 2010-07-28T03:00:10.230 回答
0
例如 - 从用于求解 eqns 的 Regula-Falsi 或 Newton-Rhapson 方法中，目的是评估每种方法的确切复杂性，然后决定（输入“n”的值或存在的任何参数）哪种方法不太复杂。
我认为非线性求解器通常无法回答这个问题。每次迭代您可以计算出准确的计算次数，但通常您永远不会知道每个求解器需要多少次迭代才能收敛。还有其他复杂情况，例如牛顿需要雅可比行列式，这可能会使计算复杂性变得更加困难。
总而言之，最有效的非线性求解器始终取决于您要解决的问题。如果您要解决的问题种类非常有限，那么使用不同的求解器进行大量实验并测量迭代次数和 CPU 时间可能会为您提供更多有用的信息。
于 2010-07-29T00:38:24.933 回答