Question

请教个算法的问题

已知有实现同一功能的两个算法，其时间复杂度分别为O(2^n)和O(n^10)，假设现实计算机可连续运算的时间为秒10^7（100多天），又每秒可执行基本操作（根据这些操作来估算算法时间复杂度）10^5次。试问在此条件下，这两个算法可解问题的规模（即n值的范围）各为多少？哪个算法更适宜？请说明理由。
解： 2^n=10^12 n=40
n^10=10^12 n=16
则对于同样的循环次数n，在这个规模下，第二种算法所花费的代价要大得多。故在这个规模下，第一种算法更适宜。

我的疑问：为什么则对于同样的循环次数n，第二种算法规模n只有16，反而代价大呢？
再劳烦大家介绍一下这一题的思路，是怎么判断的。

Answer 1

因为n代表可处理的问题的规模，对同样的操作量（连续100天运行），n越大代表处理问题
能力越强，因此第二种时间复杂度在当前运算规模下处理问题能力不够强。

下面一题，在判断时间复杂度的时候，只看多项式的最高次数。
也就是 4n^34+…… ,则只考虑最高次数n^34。

Answer 2

第一题不是很懂，没上过本科，第二题嘛，主要看指数，哪个高选哪个作为时间复杂度的级别，常数项无论是什么都没有意义

Answer 3

http://www.doc88.com/p-187699816466.html

采纳我哦

追问

我就是看的这个习题集。。。。。。。。。