如何计算算法的精确复杂度？

Question

不使用渐进符号，繁琐的步骤计算是获取算法时间复杂度的唯一方式吗？如果没有每行代码的步骤计数，我们能否得出任何程序的大O表示？

详情：尝试查找几种数值分析算法的复杂度，以决定哪种最适合解决特定问题。例如，从Regula-Falsi方法或Newton-Rhapson方法中选择一个用于解方程，意图是评估每种方法的确切复杂度，然后决定（放入“n”或任何参数）哪种方法较不复杂。

- AruniRC

Answer 1

唯一合理的方式——不是“容易”或困难的方式，而是唯一合理的方式——来找到一个复杂算法的确切复杂度就是对其进行性能分析。现代算法的实现与数字库和CPU及其浮点单元有着复杂的交互作用。例如，缓存内存访问比缓存外内存访问要快得多，而且可能存在多个级别的缓存。计算步数真的更适合于你所说的渐进复杂度，而这对你的目的来说还不够。

但是，如果你确实想自动计算步数，也有办法做到这一点。你可以在每行代码中添加一个计数器增量命令（如C语言中的“bloof ++;”），然后在最后显示该值。

你还应该了解更精细的时间复杂度表达式f(n)*(1+o(1))，它对于分析计算也很有用。例如n^2+2*n+7可以简化为n^2*(1+o(1))。如果常数因子是你关注的通常渐近符号O(f(n))的问题，这种改进是一种跟踪它并且仍然抛弃可以忽略项的方法。

- Greg Kuperberg

---

你能告诉我更多关于如何对复杂算法进行“剖析”并指向必要资源的信息吗？谢谢。 - AruniRC

请查看http://en.wikipedia.org/wiki/Profiling_%28computer_programming%29。我不是高级开发工具的专家，但那个维基百科页面可以帮助您入门。特别是它提到了经典的Unix分析命令"gprof"。 - Greg Kuperberg

Answer 2

“简单的方法”是模拟它。使用许多不同的n值和数据来尝试您的算法，绘制结果，然后将曲线与图表上的方程匹配。

您的结果可能不是严格正确的，并且仅在您生成良好的测试数据的能力有效，但对于大多数情况，这种方法都有效。

- Daniel

Answer 3

例如，在 Regula-Falsi 或 Newton-Rhapson 方法中选择一种来解决方程，意图是评估每种方法的确切复杂度，然后再决定（根据 'n' 值或其他参数）哪种方法更简单。

我认为通常情况下对非线性求解器而言，无法回答这个问题。你可以确定每次迭代的精确计算次数，但通常你无法知道每个求解器需要多少次迭代才能收敛。还有其他一些复杂因素，如需要牛顿法中的雅可比矩阵，这可能会使计算复杂度更加困难。

总之，最有效的非线性求解器始终取决于您要解决的问题。如果您要解决的问题种类非常有限，则进行一系列使用不同求解器的实验，并测量迭代次数和 CPU 时间，这将为您提供更有用的信息。

- MikeT