<演算法圖鑑>心得筆記-序章

IgorChien
3 min readSep 8, 2020

--

前言

閱讀學習後紀錄下來,以增加自己的記憶及分享學習心得。

演算法與程式差異

我個人覺得演算法就像是軍師的策略計謀,程式語言就像是要使用何種國家語言去把策略謀策編譯成卷宗或是書冊,而程式像是策略計謀的使用。

如何選擇演算法

如何去選擇一個合適的演算法,需要參考的因素有很多種。例如,簡單讓人輕鬆理解、好編譯成程式、記憶體容量小⋯⋯等因素。

但一般來說最重要的是從執行程式到完成的時間長短。

輸入大小與執行時間的關係

簡單說就是輸入大小與執行時間會成正比。

執行時間的計算方式

以執行的『步驟次數』表示執行時間。『1個步驟』當作執行的基本單位,程式運作開始到結束,共執行過多少次『步驟』來測量執行時間。

附上書中例子

・選擇排序演算法:

① 從數列中找出最小值。② 將最小值與數列最左邊的數交換,結束排序,回到 ①。

① 假設數列中有n個數量,而確認『一個數』的操作視為基本單位,耗費的時間是 T₁,所以要經過n* T₁ 的時間後結束。

②『兩個數交換』的操作也視為基本單位,耗費的時間是 T₂ 。② 的過程並不隨n變化,交換完回到 ① 。

反覆進行 ① 和 ② n次,加上每回合要確認的數會減少一個,總計的執行時間如下

(n*T₁+T₂)+((n-1)*T₁+T₂)+((n-2)*T₁+T₂)+((n-3)*T₁+T₂)+...+(1*T₁+T₂)= ½T₁(n+1)+T₂n= ½T₁n²+(½T₁+T₂)n

執行時間的表示方式

執行時間的長短,跟輸入的資料量多寡有很大的關係,也就是n的數量,而n越大,而相對其他部分就相對變小。就上述例子來說,最容易受影響的是n²。

將時間的表示方式簡化如下

½T₁n²+(½T₁+T₂)n = O(n²)

補充:

O這個符號在這表示『忽略重要項目之外的部分』(唸作order),使用這種表達方式可以直覺理解演算法的執行時間。

大O符號(英語:Big O notation),又稱為漸進符號,表示演算法的時間效能。

--

--

IgorChien

Genius is one per cent inspiration, ninety-nine per cent perspiration.學無止盡