For each function f(n) and time t in the following table, determine the largest size n of a problem that can be solved in time t, assuming that the algorithm to solve the problem takes f(n)
|
|
1 second |
1 minute |
1 hour |
1 day |
1 month |
1 year |
1 century |
|
lg n |
|
|
|
|
|
|
|
| sqrt(n) |
|
|
|
|
|
|
|
|
n |
|
|
|
|
|
|
|
|
n lg n |
|
|
|
|
|
|
|
|
n2 |
|
|
|
|
|
|
|
|
n3 |
|
|
|
|
|
|
|
|
2n |
|
|
|
|
|
|
|
|
n! |
|
|
|
|
|
|
|
这个问题看起来很简单，不过很久不碰数学分析的我，已经忘了其中几个式子的解法：
nlgn <= time的话，n的最大值是多少？ 没有精确解，不过似乎可以用逼近法算出近似值，那么这个逼近法的算法是什么呢？
同样的问题对于 n! 呢？