電腦科學基礎_4
演算法入門
- 選擇排序,Selection sort
- 大O表示法,Big O notation
- 歸併排序 - Merge sort
- Dijkstra 演算法
寫指數函式,只是無數解決方案的一種,還有其它方案。
用不同順序寫不同語句,也能得到一樣的結果,不同的是“演算法”,意思是:解決問題的具體步驟。
即使結果一致,有些演算法會更好。
一般來說,所需步驟越少越好。不過有時候也會關心其他因素,比如佔多少記憶體。
“演算法”一詞來自 阿爾●花拉子密,1000多年前的代數之父之一。
如何想出高效演算法,是早在計算機出現之前就有的問題,誕生了專門研究計算的領域,然後發展成一門現代學科,電腦科學。
選擇排序
記載最多的演算法之一是“排序”。比如給名字,數字排序。
排序到處都是,找最便宜的機票,按最新的時間排郵件,按姓氏排聯絡人等等,這些都要排序。
電腦科學家花了數十年發明了各種排序演算法,還起了酷酷的名字,“氣泡排序”, “意麵排序”,“選擇排序”
比如:
一堆機票價格,都飛往目的地。把價格一組資料存放到一個數組結構。
先找到最小數,從最上面開始,然後和第一個比較,所以看最小的數是否變化,移動位置。重複迴圈比較,持續移動位置。
意味著,如果要排N個東西,要迴圈N次,每次迴圈中再迴圈N次,共N*N。
演算法的 輸入規模 和 執行步數 之間的關係,叫演算法的 複雜度 。
表示執行速度的量級。
電腦科學家們把演算法複雜度叫:大O表示法(big O notation)。
選擇排序的演算法複雜度O(n^2)效率不高。
歸併排序
第一件事是檢查陣列大小是否>1,如果是,就把陣列分成兩半。再檢查陣列大小是否>1,如果是,繼續分組,如果不是開始“歸併”。
從前兩個陣列開始,讀第一個(也是唯一一個)值,然後開始比較,如果更小,排在之前。重複這個過程,按序排列。然後陣列大小增加,再次歸併。
同樣,取前二個數組,比較第一個數,然後再比較第一個陣列的第一個數,第二個陣列的第二個數。然後合併成更大有序的陣列。
直到排序完整。
歸併排序的演算法複雜度O(n * logn),n是需要 比較+合併的次數 和陣列大小成正比, logn
是合併步驟的次數。
圖搜尋
“圖”是用線連線起來的一堆“節點”。可以想成地圖,每個節點是一個城市,線是公路。
一個城市到另外一個城市,花的時間不同,可以用成本(cost)或權重(weight)來代稱,代表要幾個星期。
假設想找“高庭”到“凜冬城”的最快路線。
最簡單的方法是嘗試每一條路,計算總成本。這是“蠻力辦法”。
假設用蠻力方法,來排序陣列,嘗試每一種組合,看是否排好序。
這樣的時間複雜度是: O(n!)
, n
是節點數, n!
是階乘。比 O(n^2)
還糟糕。
從“高庭”開始,此時成本為0,把0標記在節點裡,其它城市標記成問號,因為不知道成本多少。 Dijkstra 演算法
總是從成本最低的節點開始,目前只知道一個節點“高庭”,所以從這裡開始,跑到所有相鄰節點,記錄成本,完成一輪演算法。
但是還未到“凜冬城”,所以再跑一次 Dijkstra 演算法
。
下一個成本最低的節點,是“君臨城”,記錄相鄰節點的成本,到“三叉戟河”,然而想記錄的是,從“高庭”到這裡的成本,所以“三叉戟河”的總成本8+5=13。現在走另外一條路到“奔流城”,成本高達25,總成本33,但“奔流城”中最低成本是10,所以無視新數字,保留之前的成本10。現在看了“君臨城”的每一條路還沒到“凜冬城”所以繼續。
下一個成本最低的節點,是“奔流城”,要10周。先看到“三叉戟河”成本,10+2=12,比之前的13好一點,所以更新“三叉戟河”為12,“奔流城”到“派克城”成本是3。10+3=13,之前是14,所以更新“派克城”為13。
“奔流城”出發的所有路徑都走了遍,還沒到終點,所以繼續。
下個成本最低的節點,是“三叉戟河”。從“三叉戟河”出發,唯一沒看過的路,通往“凜冬城”。成本是10加上“三叉戟河”的成本12,總成本是22。再看最後一條路,“派克城”到“凜冬城”,總成本是31。
所以最佳線路是:“高庭” -> “奔流城” -> “三叉戟河” -> “凜冬城”。
Dijkstra
的語錄:
“有效的程式設計師不應該浪費很多時間用於程式除錯,他們應該一開始就不要把故障引入。”
“程式測試是表明存在故障的非常有效的方法,但對於證明沒有故障,除錯是很無能為力的。”
Dijkstra 演算法
演算法複雜度是: O(n^2)
經過改造的 Dijkstra 演算法
複雜度減低為: O(n * logn + l) n是節點數,l是多少條線
資料結構
- 陣列,Array
- 字串,String
- 矩陣,Matrix
- 結構體,Struct
- 指標,Pointer
- 節點,Node
- 連結串列,Linked List
- 佇列,Queue
- 棧,Stack
- 樹,Tree
- 二叉樹,Binary Tree
- 圖,Graph
演算法處理的資料,存在記憶體裡的格式是什麼。
希望資料是結構化,方便讀取,因此電腦科學家發明了“資料結構”。
陣列
陣列Array,也叫列表(List),或向量(Vector)。有一些區別,在不同語言中基本類似。
陣列的值一個個連續存在記憶體裡。可以把多個值存在資料變數裡,為了拿出陣列中的某個值,要指定一個下標(index)
大多數程式語言中,陣列下標都從0開始。
用方括號[]代表訪問陣列。
j = [5, 3, 7, 21, 82, 4, 19] a = j[0] + j[5]
陣列存在記憶體裡的方式,十分易懂。
為了簡單,假設編譯器從記憶體地址1000開始存陣列,陣列有7個數字,像上圖一樣按順序存。
寫 j[0]
,會去記憶體地址1000,加0個偏移,得到地址1000,拿值: 5。
寫 j[5]
,會去記憶體地址1000,加5個偏移,得到地址1005,拿值: 4。
陣列的用途廣泛,所以幾乎所有的程式語言,都自帶了很多函式來處理陣列。
字串
陣列的親戚是字串String,其實就是字母,數字,標點符號等,組成的陣列。
計算機怎麼儲存字元?
通過字元對應的 ASCII表
寫程式碼時,用引號括起來就行了: j = "STAN ROCKS"
雖然長的不像陣列,但的確是陣列。
注意:字串在記憶體裡以0結尾,不是“字元0”,是二進位制“0”,這叫字元“null”,表示字串結尾。
這個字元非常重要,如果呼叫 print()
函式,會從開始位置,逐個顯示到螢幕,但是得知道什麼時候停止下來。否則會把記憶體裡所有東西都顯示出來。0告知函式何時停下。
因為計算機經常處理字串,所以有很多函式專門處理字串。