第一章 算法概述
算法的性質(zhì)
算法的四個(gè)性質(zhì)：輸入、輸出、確定性和有窮性。
算法的時(shí)間復(fù)雜度
1. 常見的時(shí)間復(fù)雜度
常數(shù)階 O(1)
對(duì)數(shù)階 O(log n)
線性階 O(n)
線性對(duì)數(shù)階 O(nlog n)
平方階 O(n^2)
立方階 O(n^3)
k 次方階 O(n^k)
指數(shù)階 O(2^n)
注：上面的 log n 均代表以2為底的對(duì)數(shù)。
2. 時(shí)間復(fù)雜度排序
常見的算法時(shí)間復(fù)雜度由小到大依次為：
Ο(1)＜Ο(log n)＜Ο(n)＜Ο(nlog n)＜Ο(n^2)＜Ο(n^3)＜ Ο(n^k) ＜ Ο(2^n)
?隨著問題規(guī)模n的不斷增大，上面時(shí)間復(fù)雜度的值也不斷增大，算法的執(zhí)行效率越來越低。
PTA習(xí)題選講
單選題
雖然沒難度，但是考了各種復(fù)雜度的排序，警醒我需要把那一串背下來！
O（1）< O（log n）< O（n）< O（nlog n）< O（n^2）< O（n^3）
靈機(jī)一動(dòng)，直接用2代入也可以！其實(shí)就是考函數(shù)的大小罷了！
?填空題
假設(shè)某算法在輸入規(guī)模為n時(shí)的計(jì)算時(shí)間為T(n)=3?2^n。
在某臺(tái)計(jì)算機(jī)上實(shí)現(xiàn)并完成該算法的時(shí)間為 t 秒。
現(xiàn)有另一臺(tái)計(jì)算機(jī)，其運(yùn)行速度為第一臺(tái)的64倍，
那么在這臺(tái)新機(jī)器上用同一算法在 t 秒內(nèi)能解決問題的輸入規(guī)模為（? ? ）。
如果算法計(jì)算時(shí)間改進(jìn)為T(n)=n^2，其余條件不變，
則新機(jī)器上用 t 秒可以解決問題的輸入規(guī)模為（? ?）。
第一小問，因?yàn)閮膳_(tái)機(jī)器的共同變量只有時(shí)間t，所以從t入手，
因?yàn)樾聶C(jī)器的速度是舊機(jī)器的64倍，所以新機(jī)器用t秒時(shí)間解決的問題規(guī)模是舊機(jī)器的64倍，
∴可得：T’(n) = 64*T(n) = 64*3*2^n = 3*2^(n+6)
問題規(guī)模和輸入規(guī)模是不同的概念，所以新機(jī)器的輸入規(guī)模應(yīng)該是 n+6?
第二小問，同理，只需要把上式的T(n)換為n^2：
T’(n) = 64*T(n) = 64*n^2 = (8*n)^2
故在這個(gè)條件下輸入規(guī)模則為 8*n
課本習(xí)題選講
1. 求下面式子的漸進(jìn)表達(dá)式：
? ? ? 21 + 1 / n
答案：O ( 1?)?
解析：求漸進(jìn)表達(dá)式，只需要將其中的n設(shè)置為無窮大即可，當(dāng)這個(gè)式子里的n為無窮大時(shí)，整個(gè)式子趨近于常數(shù)，因此漸進(jìn)表達(dá)式為常數(shù)階 O ( n ) 。
解析：O是指上界，Ω是指下界，θ是指上下界相等，在這里，可以這樣理解：
f(n) = O(g(n)) 意味著 g(n) 在 n 趨近于無窮大時(shí)比 f(n) 大；
f(n) = Ω(g(n)) 意味著 g(n) 在 n 趨近于無窮大時(shí)比 f(n) ??；
f(n) = θ(g(n)) 意味著 g(n) 在 n 趨近于無窮大時(shí)和?f(n) 同階；
因此答案如下：
（1）θ （2）O （3）Ω （4）Ω文章來源：http://www.zghlxwxcb.cn/news/detail-709443.html
（5）θ （6）Ω （7）Ω （8）O文章來源地址http://www.zghlxwxcb.cn/news/detail-709443.html
到了這里，關(guān)于【算法】算法設(shè)計(jì)與分析 課程筆記 第一章&第二章的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
