1.1 算法
算法就是把輸入轉(zhuǎn)換成輸出的計(jì)算步驟的一個(gè)序列姥闭。問題陳述說明期望的輸入/輸出關(guān)系绵患，算法則描述一個(gè)特定的計(jì)算過程來實(shí)現(xiàn)該輸入/輸出關(guān)系亿眠。問題的一個(gè)輸入序列稱為一個(gè)實(shí)例菲驴，若對于該問題的每個(gè)實(shí)例，算法都以正確的輸出停機(jī)错洁，則稱該算法正確地解決了給定計(jì)算問題。說明算法的唯一要求是必須精確描述所要遵循的計(jì)算過程戒突。
數(shù)據(jù)結(jié)構(gòu)
數(shù)據(jù)結(jié)構(gòu)是存儲(chǔ)組織數(shù)據(jù)的方法屯碴，旨在便于訪問和修改。了解基本數(shù)據(jù)結(jié)構(gòu)的優(yōu)勢和局限膊存。
難題
NP完全問題：
- 是否存在有效算法是未知的
- 任何一個(gè)NP完全問題存在有效算法导而，則所有NP完全問題都存在
- 幾個(gè)NP完全問題類似于一些已知有效算法的問題
并行性
為了從多核計(jì)算機(jī)獲得最佳性能，設(shè)計(jì)算法時(shí)考慮并行性隔崎。
練習(xí)
1.1-1 給出現(xiàn)實(shí)生活中需要排序的一個(gè)例子和計(jì)算凸殼的例子今艺。
答：搜索引擎的頁面排序、車票按價(jià)格仍稀、地點(diǎn)排序等洼滚。
凸包定義：
- 對于一個(gè)集合D，D中任意有限個(gè)點(diǎn)的線性組合的全體稱為D的凸包技潘。
- 對于一個(gè)集合D遥巴，所有包含D的凸集之交稱為D的凸包。
兩定義等價(jià)享幽。D的凸包可以用D內(nèi)所有點(diǎn)(D1铲掐，...Dn)的線性組合來構(gòu)造。在二維歐幾里得空間中值桩，凸包可想象為一條剛好包著所有點(diǎn)的橡皮圈摆霉。點(diǎn)集Q的凸包是指一個(gè)最小凸多邊形，滿足Q中的點(diǎn)或者在多邊形邊上或者在其內(nèi)奔坟。一組平面上的點(diǎn)携栋，求一個(gè)包含所有點(diǎn)的最小的凸多邊形就是凸包問題。凸包最常用的凸包算法是Graham掃描法和Jarvis步進(jìn)法咳秉。
1.1-2 除速度外婉支，在真實(shí)環(huán)境中還可能使用哪些其他有關(guān)效率的量度。
答：空間復(fù)雜度澜建、是否易于實(shí)現(xiàn)向挖、安全蝌以、維護(hù)性。
1.1-3 選擇一種你以前已知的數(shù)據(jù)結(jié)構(gòu)何之，并討論其優(yōu)勢和局限跟畅。
答：數(shù)組隨機(jī)存取容易，但插入刪除困難溶推。鏈表插入刪除容易徊件，但不能隨機(jī)存取。
1.1-4 前面給出的最短路徑與旅行商問題有哪些相似之處蒜危？有哪些不同庇忌？
答：同樣在一個(gè)圖中找最短路徑。但是約束不同：最短路僅要求兩點(diǎn)之間距離最短的路線舰褪，旅行商問題需要經(jīng)過幾個(gè)固定的點(diǎn)后回到起點(diǎn)皆疹。
1.1-5 提供一個(gè)現(xiàn)實(shí)生活的問題，其中只有最佳解才行占拍。然后提供一個(gè)問題略就，其中近似最佳解也足夠好。
答：圖像晃酒、語音識(shí)別要求準(zhǔn)確率高才有實(shí)際用途”砝危現(xiàn)實(shí)兩城市之間的最短路近似最佳即可。
1.2 作為一種技術(shù)的算法
效率
求解相同問題的不同算法在效率上有顯著差別贝次。以排序?yàn)槔扌耍迦肱判驈?fù)雜度O（n^2），歸并排序O（nlgn）蛔翅。小規(guī)模輸入插入排序通常更快敲茄，但超過一個(gè)交叉點(diǎn)后歸并排序更快，且問題規(guī)模越大優(yōu)勢越大山析。
練習(xí)
1.2-1 給出在應(yīng)用層需要算法內(nèi)容的應(yīng)用的一個(gè)例子堰燎，并討論涉及算法的功能。
答：地圖導(dǎo)航笋轨，需要最短路算法秆剪。
1.2-2 假設(shè)我們正比較插入與歸并排序在相同機(jī)器上的實(shí)現(xiàn)。對規(guī)模為n的輸入爵政，插入排序運(yùn)行
步仅讽，而歸并排序運(yùn)行64nlgn步。問對哪些n值钾挟，插入排序優(yōu)于歸并洁灵？
答：
8n^2 < 64nlgn
n < 8lgn
解得n < 43。即43步以內(nèi)插入排序更快等龙。
1.2-3 n的最小值為何值時(shí)处渣，運(yùn)行時(shí)間為100n2的算法在相同機(jī)器上快于運(yùn)行時(shí)間為2n的另一個(gè)算法？
答：
100n^2 < 2^n 解得n > 14蛛砰。
1-1 運(yùn)行時(shí)間比較
