題目的回答會(huì)整理并在gayhub更新
期待在評(píng)論區(qū)討論問(wèn)題
1.2-3
原題：
n的最小值為何值時(shí)卦绣，運(yùn)行時(shí)間為100n2的一個(gè)算法在相同機(jī)器上快于運(yùn)行時(shí)間為2n的另一個(gè)算法？
回答：
函數(shù)圖像
函數(shù)圖像
藍(lán)色的是100n2飞蚓，綠色的是2n滤港。
第一張是定義域[0,2]的圖像。第二張是定義域[0,50]的圖像趴拧，為了展示效果比例有點(diǎn)扭曲蜗搔。
從第一張圖可以看到，大概n<=0.1(實(shí)際大點(diǎn))的時(shí)候八堡，藍(lán)線更優(yōu)。從第二張圖可以看到聘芜，大概n>=15(實(shí)際更大一點(diǎn)點(diǎn))時(shí)候兄渺，同樣藍(lán)線更優(yōu)
所以如果n取整而不為零，那么答案就是n=15汰现。
思考題1
1-1
(運(yùn)行時(shí)間的比較) 假設(shè)求解問(wèn)題的算法需要f(n)毫秒挂谍， 對(duì)下表中的每個(gè)函數(shù)f(n)和時(shí)間t，確定可以在時(shí)間t內(nèi)求解的問(wèn)題的最大規(guī)模n瞎饲。
| 1秒鐘 | 1分鐘 | 1小時(shí) | 1天 | 1月(30天) | 1年(365.24天) | 1世紀(jì) | |
|---|---|---|---|---|---|---|---|
| log2n | 1x10301 | ||||||
| n0.5 | 1x106 | 3.6x109 | 12.96x1012 | 7.46x1015 | 6.74x1018 | 9.95x1020 | 9.95x1024 |
| n | 1x103 | 6x104 | 3.6x106 | 8.64x107 | 2.6x109 | 3.16x1010 | 3.16x1012 |
| nlog2n | 140 | 4895 | 2.04x103 | 3.94x104 | 9.77x105 | 1.05x107 | 8.68x1010 |
| n2 | 31.6 | 244.9 | 1897 | 9295 | 5x104 | 1.78x105 | 1.78x106 |
| n3 | 10 | 39.1 | 153.3 | 442.1 | 1373 | 3160 | 1.474 |
| 2n | 9 | 15 | 21 | 26 | 31 | 34 | 41 |
| n! | 6 | 8 | 9 | 11 | 12 | 13 | 15 |
