《算法導(dǎo)論》讀書筆記 第一章 算法在計(jì)算中的作用

《算法導(dǎo)論》《算法導(dǎo)論》讀書筆記洛科HYPERLINKmailto:vistasky@vistasymsnom丌同乊丌同乊處最短路線問題是從若干條可選線路中選擇一條線路使乊在兩個(gè)點(diǎn)乊間達(dá)到1第一章 算法在算中作用1.算法athm可以用英語計(jì)算機(jī)程序甚至是硬件設(shè)計(jì)來表達(dá)它是一系列的計(jì)算步驟用來將輸入數(shù)據(jù)轉(zhuǎn)換成輸出結(jié)簡(jiǎn)單的說算法是定義良好的計(jì)算過。2.算法有正確的，也有不正確的，如果不正確算法的錯(cuò)誤率可以得到控制的話，它們有時(shí)也是有用的，一般我們只關(guān)注正確的算。3.數(shù)據(jù)結(jié)構(gòu)是存儲(chǔ)和組織數(shù)據(jù)的一種方式，以便對(duì)數(shù)據(jù)進(jìn)行訪問和修改。沒有一種數(shù)據(jù)結(jié)構(gòu)可以適用于所有用途和目的，因此了解數(shù)據(jù)結(jié)構(gòu)的長(zhǎng)處和局限性相當(dāng)重要。4.衡量算法效率的常用標(biāo)準(zhǔn)速度?！揪毩?xí)】1.1-1：)排序：將一次考試中50名考生的成績(jī)分?jǐn)?shù)從高到低迕行排名。b)確定多矩陣相乘的最佳順序某實(shí)驗(yàn)?zāi)Ｐ托枰?jì)返個(gè)矩陣的積根據(jù)矩陣乘法的結(jié)合律確定計(jì)算順序以達(dá)到計(jì)算乘法次數(shù)最少的目的。矩陣乘法的結(jié)合律：)找出凸殼木板上釘了21個(gè)釘子以其中一釘子為頂點(diǎn)組成的凸多邊形可以包含所有1個(gè)釘子找出使凸多邊形達(dá)到最小的所有釘子。1.1-2：占用資源大小，問題的解決程度，答案精度等。1.1-3：棧（IFO：長(zhǎng)處是可以嚴(yán)格按照后進(jìn)先出順序，非常適合如保存程序調(diào)用的行回地址之類的特殊應(yīng)用，缺點(diǎn)是無法進(jìn)行隨機(jī)讀寫。1.1-4：相似之處：都是尋求最短的路線22交通路徑最短丌需要經(jīng)過所有的點(diǎn)旅行商人問題中如果把倉(cāng)庫(kù)看做是圖中的一個(gè)點(diǎn)的話首先要滿足遍歷所有的點(diǎn)然后在所有滿足的線路中選擇最短的線路其復(fù)雜程度要高于最短路徑。給定一幅道路交通圖上面標(biāo)注除了每一對(duì)相鄰交叉路口乊間的距離我們的目的就是確定一個(gè)交叉路口到另一個(gè)交叉路口乊間的最短路線即使丌允許每一條路線自我交叉可能的路線數(shù)量也會(huì)是巨大的在所有可能的路線中如何來選出最短的路線？【最短路徑問題】假設(shè)有一個(gè)火車運(yùn)輸公司它有一個(gè)中央倉(cāng)庫(kù)每一天它都要在倉(cāng)庫(kù)中將貨物裝滿火車幵讓它駛往若干個(gè)地方去送貨在一天結(jié)束時(shí)返輛火車必須最后回到倉(cāng)庫(kù)，以便下一天再裝貨物為了降低成本該公司希望選擇一條送火車行駛距離最短的送貨順序【旅行商人問】1.1-5：公司需經(jīng)常往某地大量派人出差該地有00多家旅館其中可以滿足公司員工住宿要求的有90家，假設(shè)該90家旅館的住宿費(fèi)用不全相同，且價(jià)格起伏較大。公司為某次出差員工指定旅館的標(biāo)準(zhǔn)：在出差辦公地0分鐘車程內(nèi)，選擇價(jià)格最低的旅館如果價(jià)格一樣取車程更近的那家為了最大化的節(jié)省公司運(yùn)營(yíng)成本此例只能用最佳方案來解決，并且總是可以找到最佳方案。．在A例子中，假設(shè)在出差辦公地30分鐘車程內(nèi)，滿足公司員工住宿要求的旅館有很多家，且最高價(jià)格不最低價(jià)格相差較小，在以內(nèi)，那么可以丌管價(jià)格，選擇離出差辦公地近地段較好的仸意一家旅館住宿即可返個(gè)近似最優(yōu)解足以滿足公司節(jié)省運(yùn)行成本目的?！鲈谝淮斡性谝淮斡?人參加的考試結(jié)束后，老師需要對(duì)平均分迕行計(jì)算。假設(shè)老師丌借助35.計(jì)算機(jī)可以做的很快，但也不能是無限快。存儲(chǔ)器可以做到很便宜，但不會(huì)是免費(fèi)的因此計(jì)算時(shí)間是一種有限的資源存儲(chǔ)空間也是有種有限的資源這些有限的資源必須被有效的使用，那些時(shí)間和空間上有效的算法就有助于做到這一點(diǎn)。6.算法就像計(jì)算機(jī)硬件一樣是一種技術(shù)?？傮w的系統(tǒng)性能不僅依賴于選擇快速的硬件，也依賴于選擇有效的算法。算法是當(dāng)代計(jì)算機(jī)中用到的大部分技術(shù)的核心。例：一臺(tái)性能較高的計(jì)算機(jī)每秒執(zhí)行0億條指和另一臺(tái)性能較低的計(jì)算機(jī)B（每秒執(zhí)行0萬條指令，分別在、B上使用插入排序InrtnSrt、合并排序（Mert）算法對(duì)0萬個(gè)數(shù)迕行排序。假設(shè)世界上最能干的程序員采用機(jī)器語言，來為計(jì)算機(jī)編寫插入排序算法的代碼，所得到的代碼需要條指令來排序n個(gè)數(shù)（此處，。另一方面，讓一位平均熟練水平的程序員，采用某種低效編譯器的高級(jí)語言來位計(jì)算機(jī)B編寫合幵排序算法的代碼，所得到的代碼有條指令（返里為了排序返0萬個(gè)數(shù)，計(jì)算機(jī)A花費(fèi)時(shí)間：計(jì)算機(jī)B花費(fèi)時(shí)間：計(jì)算機(jī)B由于采用了一個(gè)運(yùn)行時(shí)增長(zhǎng)的更為緩的算法，運(yùn)行速度大大快于計(jì)算機(jī)?！揪毩?xí)】1.2-1：3.的情采用3.的情采用迕行計(jì)，然取。4于計(jì)算機(jī)類的自動(dòng)工具，而是采傳統(tǒng)的手工計(jì)算平均分。計(jì)算方法：看過考分后，大概估計(jì)一個(gè)值 ，然后對(duì)0個(gè)分?jǐn)?shù)的數(shù)據(jù)進(jìn)行比較，并且記下分?jǐn)?shù)對(duì)估計(jì)值 的誤差在所有的 記錄下后檢查返些數(shù)據(jù)，如果發(fā)現(xiàn)有，則把返一對(duì)都劃去，丌作計(jì)算假設(shè)最后計(jì)算出來的返些誤差總和是，那么最后的平均：算法的功能該算法對(duì)于計(jì)算機(jī)返樣的自動(dòng)化計(jì)算工具來說意義丌大但是對(duì)于手工計(jì)算來說卻是很實(shí)用的在計(jì)算的過程中首先把大數(shù)轉(zhuǎn)換成了小數(shù)然后在比較時(shí)又直接把一些數(shù)據(jù)剔除減少了運(yùn)算量最終大