Aru*_*iRC 5 algorithm numerical-analysis numerical-methods
如果不采用渐近符号,计算获得算法时间复杂度的唯一方法是乏味的步骤吗？如果没有每行代码的步数,我们可以得到任何程序的大O表示吗？
细节:试图找出几种数值分析算法的复杂性,以确定哪种算法最适合解决特定问题.例如 - 从用于求解方程的Regula-Falsi或Newton-Rhapson方法中,意图是评估每个方法的确切复杂性,然后决定(设置'n'或其他任何参数的值)哪个方法不那么复杂.
唯一的方法 - 不是"简单"或艰难的方式,而是唯一合理的方法 - 找到复杂算法的确切复杂性就是对其进行分析.算法的现代实现具有与数字库以及CPU及其浮点单元的复杂交互.例如,高速缓存内存访问比高速缓存内存访问快得多,最重要的是可能有多个级别的高速缓存.计数步骤实际上更适合渐近的复杂性,你说这对于你的目的是不够的.
但是,如果你确实想要自动计算步数,那么也有办法做到这一点.您可以在每行代码中添加一个计数器增量命令(如"C中的"bloof ++;"),然后在结尾处显示该值.
您还应该了解更精细的时间复杂度表达式f(n)*(1 + o(1)),这对分析计算也很有用.例如,n ^ 2 + 2*n + 7简化为n ^ 2*(1 + o(1)).如果恒定因子是通常的渐近符号O(f(n))困扰你的话,这种改进是一种跟踪它并仍然抛出可忽略的术语的方法.