如果不求助于渐近符号,单调的步数是否是获得算法时间复杂度的唯一途径?如果不计算每行代码的步数,我们能否得出任何程序的大 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)) 感到困扰,那么这种改进是一种跟踪它并仍然抛出可忽略项的方法。
关于algorithm - 如何计算算法的确切复杂度?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3349557/