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

不使用渐近表示法，是计算获得算法时间复杂度的唯一方法的单调乏味的步骤？如果没有每行代码的步数，我们是否可以得到任何程序的大O代表？如何计算算法的确切复杂度？

详细信息：试图找出几种数值分析算法的复杂性，以决定哪种最适合解决特定问题。例如 - 从Regula-Falsi方法或Newton-Rhapson方法中求解eqns，意图是评估每种方法的确切复杂性，然后决定（把'n'的值或任何参数），哪种方法不那么复杂。

来源

2010-07-28 AruniRC

唯一的方法---不是“简单”或困难的方法，但唯一合理的方法---找到一个复杂算法的确切复杂性是分析它。算法的现代实现与数值库以及CPU和浮点单元之间存在复杂的交互。例如，高速缓存内存访问比高速缓存内存访问要快得多，并且最重要的是可能有多个级别的高速缓存。计算步骤实际上更适合于你认为不够用于你的目的的渐近复杂性。

但是，如果您确实想自动计算步骤，也有办法做到这一点。您可以在每行代码中添加一个计数器递增命令（如C中的“bloof ++;”），然后在末尾显示该值。您还应该了解更精确的时间复杂度表达式f（n）*（1 + o（1）），这对分析计算也很有用。例如n^2 + 2 * n + 7简化为n^2 *（1 + o（1））。如果常数因子是关于通常渐近符号O（f（n））的困扰，那么这种细化是一种跟踪它的方法，并且仍然抛出可忽略的项。

来源

2010-07-28 04:57:34

简化将有帮助谢谢。你能告诉我更多/指向我如何'分析'复杂算法的必要资源。 – AruniRC 2010-07-29 05:15:25

请参阅http://en.wikipedia.org/wiki/Profiling_%28computer_programming%29。我不是花哨的开发工具的专家，但是维基百科页面可以帮助您开始。特别是，它提到了经典的Unix分析命令“gprof”。 – 2010-07-29 14:25:35

'简单的方法'是模拟它。尝试使用大量n值和大量不同数据的算法，绘制结果，然后将图上的曲线与方程进行匹配。

您的结果可能不是严格正确的，它们只与您生成良好测试数据的能力一样有效，但对于大多数情况下这将起作用。

来源

2010-07-28 03:00:10 Daniel

例如， - 从Regula-Falsi方法或Newton-Rhapson方法中求解eqns，意图是评估每种方法的确切复杂性，然后决定（把'n'的值或任何参数），哪种方法不那么复杂。

对于非线性求解器，我不认为一般可以回答这个问题。你可以在每次迭代中进行确切的计算次数，但是你永远不会知道每个求解器需要进行多少迭代才能收敛。还有其他一些复杂问题，比如需要用牛顿的雅可比行列式，这可能会使计算复杂度变得更加困难。

总之，最有效的非线性求解器总是依赖于你正在解决的问题。如果您正在解决的各种问题非常有限，那么使用不同求解器进行一系列实验并测量迭代次数和CPU时间可能会为您提供更多有用的信息。

来源

2010-07-29 00:38:24 MikeT

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

回答

相关问题