第一章 算法在計算中的作用

本章主要介紹了算法的概念、算法的用途、算法的意義等，并做了后續(xù)章節(jié)的部分概括。
算法實際上就是對于外界輸入進行處理并給出符合預(yù)期輸出的計算過程，書上的概念是：“對于任何良定義的計算過程，該過程取某個值或值的集合作為輸入并產(chǎn)生某個值或值的集合作為輸出。”
可以把算法理解為轉(zhuǎn)換輸入與輸出的一個過程。
算法可以解決很多生活中的實際問題，包括DNA測序、快速搜索等，應(yīng)用范圍十分廣泛。
算法解決問題有兩個共同特征：存在許多候選解與存在實際運用。
數(shù)據(jù)結(jié)構(gòu)是一種存儲和組織數(shù)據(jù)的方式，各有優(yōu)劣。
另外算法設(shè)計還需要考慮程序并行性。
習(xí)題答案：
1.1-1：給出現(xiàn)實生活中需要排序的一個例子或者現(xiàn)實生活中需要計算凸殼的一個例子。
答：同類型商品按價格進行排序擺貨銷售；地產(chǎn)開發(fā)中根據(jù)幾個點確定開發(fā)面積。
1.1-2：除速度外，在真實環(huán)境中還可能使用哪些其他有關(guān)效率的量度？
答：空間的占用率、穩(wěn)固程度等（只能短暫快速使用同樣效率低下）。
1.1-3：選擇一種你以前已知的數(shù)據(jù)結(jié)構(gòu)，并討論其優(yōu)勢與局限。
答：鏈表。鏈表很容易刪除與插入，但是卻不方便查找，需要O（N）的復(fù)雜度；數(shù)組方便查找，但不方便刪除與插入。
1.1-4:前面給出的最短路徑與旅行商問題有哪些相似之處？又有哪些不同？
答：相似之處在于都是在給定的條件下求最短路徑，但不同之處在于TSP！=The Shortest Path.因為TSP是要求經(jīng)過每個點的最小環(huán)路，而最短路徑只是求從起點到終點的最短距離。
1.1-5：提供一個現(xiàn)實生活的問題，其中只有最佳解才行。然后提供一個問題，其中近似最佳的一個解也足夠好。
答：購買相同的商品，到距離自身最近的店購買是最優(yōu)解。
這里參考“背包問題”，可以使用動態(tài)規(guī)劃與組合優(yōu)化思想求得近似最優(yōu)解。

使用算法的根本原因：空間、時間有限且寶貴。
這里書中采用了歸并排序與插入排序作了比較，插入排序:O(N^2),歸并排序：O(NlogN)。數(shù)據(jù)量越大，差距也就越大。
值得注意的是：算法是現(xiàn)代大部分計算機使用技術(shù)的核心！
習(xí)題答案：
1.2-1：給出在應(yīng)用層需要算法內(nèi)容的應(yīng)用的一個例子，并討論涉及的算法的功能。
答：對教師工資/學(xué)生成績進行排序。
（更快、更準(zhǔn)確地排序。）
1.2-2：假設(shè)我們正比較插入排序與歸并排序在相同機器上的實現(xiàn)。對規(guī)模為n的輸入，插入排序運行8N^2步，而歸并排序運行64NlgN步。問對于哪些N值，插入排序優(yōu)于歸并排序？
答：我們知道N^2 的增長趨勢一定高于NlgN，所以一定存在某個N值，使得當(dāng)n>N時，8N^2>64NlgN。即求 N/8lgN > 1的臨界值。
易知N=44時滿足上式。
所以N=1…43時插入排序都優(yōu)于歸并排序。
注：lgN是以2為底。
1.2-3：n的最小值為何值時，運行時間為100n^2的一個算法在相同機器上快于運行時間為2 ^n的另一個算法？
答：即求前者小于后者的對應(yīng)最小N值。
計算可得 N 最小值為：15。

思考題：

體會不同f(n)需要的時間規(guī)模即可，計算從略。

總結(jié)

以上是生活随笔為你收集整理的算法导论（原书第三版）答案与学习笔记（一）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。