运算量 n！ 2^n n^3 n^2 nlogn n
最大规模 11 26 464 10000 4.5*10^6 1000000000
速度扩大两倍 11 27 587 14142 8.6*10^6 2000000000
这个表给出了机器速度扩大两倍后，算法所能解决的规模的对比。可以看出，n！和2n不仅能解决的问题规模十分小,而且增长缓慢；最快的nlogn和n算法不仅解决问题
的规模大，而且增长快。我们把渐进时间复杂为多项式的算法称为多项式时间算法(polymonial-time algorithm)，也称有效算法；而n!或者2^n这样低效算法称为指数时间算法（exponential-time algorithm）.
尽管如此，考虑到目前主流机器的执行速度，多数算法竞赛所选取的数据规模基本符合此表。例如，一些指明n<=8的题目，可能n！的算法已经足够，n<=20的题目需要2^n的算法,而n<=300的题目可能就需要用至少n^3的多项式算法.
版权声明：本文为Hashmat原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。