这两个算法哪个的速度快？

Question

已知有实现同一功能的两个算法，其时间复杂度分别为O(2^n)和O(n^10)，假设现实计算机可连续运行的时间为100天，又每秒可执行基本操作为10^5次。试问在此条件下，这两个算法可解决问题的规模（即n的范围）各为多少？哪个算法更合适？试说明理由不能用电脑和计算器，这题该咋做？

Answer 1

动笔算一算就出来了：100天=100*24*60*60秒
又，一秒钟可执行的基本操作为10^5次
则，100天可执行的基本操作为100*24*60*60*(10^5)=864000000000次分别解方程：2^x=864000000000 ---- (1)x^10=864000000000-----(2)由方程(1)可估计出x在39-40之间，所以算法的最大规模为39
由方程(2)可估计出x在15-16之间，所以算法的最大规模为15所以在当前条件下，用算法一更好。但是，算法一的复杂度是指数级的，算法二的复杂度是乘方级（10次方）的，通常指数级的增长速度快于乘方级，虽然2^n一开始增长较慢，但速度更快，所以一旦n增长到某个临界点之上，算法一耗费的时间最终将更多。至于这个临界点是多少，算起来太麻烦了，可能要借助计算机。