DAY 02 : 演算法基本概念

2.1 甚麼是演算法?

演算法是解決特定問題以求解步驟的描述，在電腦中為指令的有限序列，且每條指令表示一個或多個操作，對於給定的問題可用多種演算法解決。

2.2 演算法特性

輸入(Input):不一定要有輸入。
輸出(Output):一定會有輸出，輸出的性質可以是列印輸出、回傳1或多個值等。
有限性(finiteness):執行有限的步驟，在合理且可接受的時間內，會自動結束且不會出現無限迴圈。
確定性(definiteness):演算法的每一個步驟都有確定的含意，不會有定義不清楚的狀況出現，相同的輸入只會有唯一的輸出結果。
可行性(effectiveness):演算法的每一個步驟都是可執行的，也就是可以轉換成程式。

2.3 好的演算法特性

正確性:演算應至少具有輸入、輸出、執行處理無歧義性、能正確反映問題需求，並且能得到正確答案。
｢正確」可分為四個層次:
層次一:沒有語法錯誤(太基本了不足以稱為好的演算法)。
層次二:對於合理的輸入資料會產生滿足要求的輸出結果。
層次三:對於不合理的輸入資料會產生滿足規格說明的結果。(在一般情況下，以此層次作為正確的標準)。
層次四:即使是精心準備的、刁難人的測試資料都能產生滿足要求的輸出結果(難以達成)。
可讀性:演算法便於自己也便於他人閱讀、理解和交流。
健壯性:當輸入資料不合理時，演算法能做出合理的處理方式，而非產生異常或是莫名其妙的結果。
高效率和低存取量:執行的時間短，執行過程中所需的最大儲存空間最小。

2.4 演算法效率的度量法

演算法效率的度量法分為以下兩種:

事後統計法:先將程式個用不同的演算法撰寫好，再利用電腦的計時器來計算不同的演算法所撰寫的程式執行時間的差異，進而得知效率高低。

缺點一:需事先將所有程式撰寫完成，總而言之就是麻煩。
缺點二:易因為作業系統、編譯器、運行框架的不同，又或者是因為CPU使用不同等原因而掩蓋掉演算法本身的優劣。
缺點三:受測試資料規模影響，小規模測試看不出演算法優劣，大規模測試便有可能慘生極大的差異。

事前分析估算法:是運用數學的統計方法進行演算法效率的估算。一個演算法的效率高低主要取決於演算法的好壞和問題的輸入規模(分析出某個演算法和數值n的關係)。
測量執行時間最靠譜的方法就是分析基本操作的執行次數。使用事前分析估計法不需考慮使用何種程式語言或是在和整電腦執行，只需在意它的演算法就可以。此外，在分析執行時間時須將程式視為獨立於程式語言的演算法或是步驟，須將基本操作的數量表示成輸入規模函式。

輸入規模函式具有漸近增長的特性:在輸入規模n是沒有限制的情況下，當超過某一數值N，此函式的執行次數就會永遠大於另一個函式，在計算函式時我們會忽略常數也會忽略與最高項相乘的常數，因為對結果影響不大，而最高次項的指數影響就較大。
假設有兩個函式分別式f(n)和g(n)，如果存在一個整數N，且所有的n>N，當f(n)始終大於g(n)，則f(n)會逐漸增長的比g(n)快。

2.5時間複雜度O(n)

時間複雜度用來表示執行時間的需求

總執行次數T(n)=演算法的時間複雜度O(f(n))
代表執行時間的增長率和f(n)的增長率相同，稱為時間複雜度，O(n)稱為｢Big O符號」。

常數階:為循序敘述、單純決策分支敘述的時間複雜度，用常數1取代執行時間中的所有加法常數，ex:f(n) = 3，時間複雜度為O(1)
線性階:分析迴圈結構(當程式碼須被執行n次)的執行狀況時，其時間複雜度為線性階O(n)。
對數階:O(log n)
平方階:O(n^2)，ex:f(n)=n^2/2 + n/2，其時間複雜度為O(n^2)