最优算法

来自计算思维百科
跳转至: 导航搜索

最优算法(Optimal Algorithm)是从时间复杂度角度定义的,未考虑算法的空间复杂度。主要原因是:只要在一个合理的范围里使用空间,时间的考虑比空间更宝贵。

一个问题的最优算法是指:如果能够证明求解该问题的任何算法在最坏情况下的运行时间下界是f(n),那么,以时间o(f(n))来求解该问题的任何算法都认为是最优算法。

如果有两个算法都是最优算法,就需要进一步比较两个算法时间复杂度表达式中高阶项常数因子。常数因子小的算法优于常数因子大的算法。