解决同一个问题的两种方法,一个是时间复杂度为0(3^n),另一个是0(n^9),系统7×24小时运行,每秒钟执行基本运算10^8次.问这两种方法分别可以计算多大规模的问题?相比而言哪种效率高?

Question

解决同一个问题的两种方法,一个是时间复杂度为0(3^n) ,另一个是0(n^9) ,系统7×24小时运行,
每秒钟执行基本运算10^8 次.问这两种方法分别可以计算多大规模的问题?相比而言哪种效率高?

Answer 1

总的运行次数为7×24×3600×10^8
对于第一个,则为3^n1 = 7×24×3600×10^8,可以解得n1 = 28.885
对于第二个,则为n2^9 = 7×24×3600×10^8,可以解得n2 = 33.985
效率自然是后面的高,当然,如果时间再短点,也可能会前面的效率高
其实前面的是指数,后面的是多项式,理论原则也是多项式的效率高