Problem 1-1
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)\) microseconds.
\[
\begin{array}{cccccccc}
& \text{1 second} & \text{1 minute} & \text{1 hour} & \text{1 day} & \text{1 month} & \text{1 year} & \text{1 century} \\\\
\hline
\lg n & 2^{10^6} & 2^{6 \times 10^7} & 2^{3.6 \times 10^9} & 2^{8.64 \times 10^{10}} & 2^{2.59 \times 10^{12}} & 2^{3.15 \times 10^{13}} & 2^{3.15 \times 10^{15}} \\\\
\sqrt n & 10^{12} & 3.6 \times 10^{15} & 1.3 \times 10^{19} & 7.46 \times 10^{21} & 6.72 \times 10^{24} & 9.95 \times 10^{26} & 9.95 \times 10^{30} \\\\
n & 10^6 & 6 \times 10^7 & 3.6 \times 10^9 & 8.64 \times 10^{10} & 2.59 \times 10^{12} & 3.15 \times 10^{13} & 3.15 \times 10^{15} \\\\
n\lg n & 6.24 \times 10^4 & 2.8 \times 10^6 & 1.33 \times 10^8 & 2.76 \times 10^9 & 7.19 \times 10^{10} & 7.98 \times 10^{11} & 6.86 \times 10^{13} \\\\
n^2 & 1000 & 7745 & 60000 & 293938 & 1609968 & 5615692 & 56156922 \\\\
n^3 & 100 & 391 & 1532 & 4420 & 13736 & 31593 & 146645 \\\\
2^n & 19 & 25 & 31 & 36 & 41 & 44 & 51 \\\\
n! & 9 & 11 & 12 & 13 & 15 & 16 & 17
\end{array}
\]
本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供,附加条款亦可能应用