Coursera – Algorithmic Toolbox 第二週學習筆記

Why Study Algorithms?

  1. 有些問題(例如:逐字複製文件內容)只能採用最直覺的演算法,無法再進行優化。
  2. 有些問題(例如:兩點之間的最短距離、文件內容相似性的比較)除了最直覺的演算法,還能採用其他效率更高的演算法。
  3. 另外,Artificial Intelligence(AI) Problems(例如:使程式具有理解人類自然語言的能力、辨識圖片中的物件、下棋)較難產生演算法,也就是較難清楚陳述解決問題的執行步驟(例如:需要具備分析英文語法的知識)。
  4. 這堂課的重點著重於:對於定義明確但直覺演算法效率較差的問題進行優化,寫出效率更高的演算法,而非發展與AI相關的演算法。但這種訓練將成為日後學習AI相關演算法的基礎。
  5. 之後的課程內容將探討計算Fibonacci numbers和Greatest common divisors(最大公因數)等問題,這兩種問題都有步驟簡單但效率極差的演算法,可以讓我們體會到演算法在優化前後的執行效率有大幅的改善。

Fibonacci Numbers

  1. Fibonacci Numbers數值序列一開始是為了計算兔子的生育數量。
  2. Fibonacci Numbers數值序列如下,F(0) = 0,F(1) = 1,F(n) = F(n-1) + F(n-2),以此類推。
  3. 對於任何給定的n值,若欲求取F(n)的數值,最直覺的方式是根據F(0) = 0和F(1) = 1作為初始條件,再採用F(n) = F(n-1) + F(n-2)進行遞迴(Recursive)運算,亦即函數會重複呼叫自己,但給予不同的參數。
  4. 遞迴函數的效率很差,因為相同的函數、參數可能備重複運算多次。例如為了運算的F(5)時,需遞迴運算F(4)和F(3),然而在運算F(4)時,又需要遞迴運算F(3)和F(2),至此,F(3)已經被重複運算了兩次。
    當F(n)中的n愈大時,重複運算相同函數和參數的比例將愈大。
  5. 另外一個較有效率的演算法:計算F(n)時,先產生size為n的陣列,陣列的第0個item放置0,第1個item放置1,採用For迴圈,一一根據第x-1個、第x-2個item計算出第x個item的數值,最終求得第n個item的數值,即為F(n)。

Greatest common divisors

  1. 當a, b兩個整數都大於0,而存在一個可以同時整除a和b的最大正整數,即為a和b兩者的最大公因數(可標記為gcd(a, b))。
  2. 較直覺的演算法是:執行迴圈檢查1~a+b範圍中的每個數值,一一檢查是否可以同時整除a和b,
    假如可以整除即為公因數,再判斷其是否為比"目前已知的最大公因數"更大,若"是"則取而代之,成為新的最大公因數。當迴圈執行結束,則可得到最終版本的最大公因數。
  3. 有另外一種較有效率的演算法:假設a > b且a,b > 0,先用a % b取得餘數c,再用b % c取得餘數d,
    以此類推,直到 x % 0 ,則x即為a和b的最大公因數。

Big-O Notation

  1. 如果需要準確的知道程式實際執行時間(Runtime),至少必須知道以下資訊:
  2. 電腦運算速度
  3. 電腦硬體所採用的架構
  4. 倘若是使用編譯式語言撰寫的程式,還必須考慮所採用的編譯器,因為編譯器將編譯語言轉換成機器語言時會進行一下效能的最佳化,不同編譯器的效能最佳化成效也將不同,進而影響編譯過的程式執行時間。
  5. 記憶體階層架構。
  6. 程式碼的行數, 以及每一行程式碼分別實際執行的運算動作。運算動作不同時,所需花費的執行時間也不同。
  7. 受上述因素的影響,相同的程式在不同的電腦上執行時,實際所需的執行時間將不盡相同。因此在分析演算法的執行時間時,可以採用Big-O的方式,根據演算法的程式碼的流程控制和程式碼的數量,評估演算法的執行時間隨著input大小成長的成長幅度數量級(log n < log n^(1/2) < n < n (log n) < n^2 < 2^n)。
  8. 採用O(n)具有以下優點:
  9. 可以在不需要考慮硬體設備等資訊的情況下,快速評估演算法的執行時間隨著input成長的成長幅度。
  10. 方便依此比較不同演算法在input極大時的優劣。
  11. 可以快速找出效率不佳的演算法,例如: 評估結果為O(n^2), O(2^n)的演算法。
  12. 採用O(n)具有以下缺點:
  13. 倘若程式實際執行時採用的input大小都不大時,可能無法根據Big-O準確比較出不同演算法的優劣。
  14. Big-O只能評估演算法的執行時間隨著input成長的成長幅度數量級,是一個相對性概念,其無法得到絕對性概念的程式實際執行時間。
  15. Big-O忽略了常數項,例如:倘若有兩個演算法的程式行數分別為(100n+2) 和n,他們的效率相差了將近100倍,但都為O(n)。因此Big-O適合用來進行效能優劣的初步比較,實際上要持續優化程式效率時,仍應嘗試各種方法使常數項被優化。
廣告

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s