演算法基本概念 : Communicate within Algorithm
前言
這篇文章是我在修讀 MIT 的 Introduction to Algorithm 後所節錄下來的學習心得，主要是想記錄那些我們在討倫演算法時會常用到的基本觀念，瞭解這些內容可以幫助我們更進一步的與他人有溝通上的一致性。
Big O : Asymptotic Notation (漸進符號)
前面有提到，在提出演算法時我們最關注的兩個面向分別是正確性還有效率(或正確地來說執行時間)。正確性可以透過數學歸納法或是其他論證方法等來驗證，有效性則可以透過兩種方法來進行驗證:
- 撰寫程式執行並測量時間
- 用看的，觀察執行時間隨資料擴增的變化趨勢
測量執行時間雖然是最直接的方法，但其結果會隨機器之間不同性能而有所影響，因此在討論執行效率時較常用演算法的計算次數來辨識，而計算次數又受輸入參數的規模大小有所影響，因而有了漸進表示法的引入。
什麼是漸進符號 (Asymptotic Notation) ?
根據維基百科的定義:
白話的來說，漸進表示法旨在探討當輸入的資料規模變得越來越大，演算法的計算行為是否也會跟著增加? 增加的幅度變化又是如何? 因此漸進表示法不等於演算法確切的執行時間。
舉例來說，若對任意輸入的資料大小進行某一操作能以固定的計算次數完成 (Constant Time)，則當輸入的資料非常大時演算法也可以同樣的計算次數完成，這就是一個具有極佳效率的方法。
資料結構 (Data Structure) 與介面 (Interface)
資料結構是一種儲存動態資料的方法，並且滿足一系列共通的資料操作方法。
介面是一組對資料操作方法的集合。可以說介面定義了那些操作是可行的 (問題)，而資料結構定義了如何實踐這些操作方法 (問題的答案)。
同一個介面可以用不同資料結構的方式來實踐。
平攤分析 (Armotized Analysis)
攤銷分析是一種分析算法時間複雜度的方法，通常用於評估一個算法的平均性能。根據維基百科的定義:
The motivation for amortized analysis is that looking at the worst-case run time can be too pessimistic. Instead, amortized analysis averages the running times of operations in a sequence over that sequence.
大意是說，演算法中某項操作在當下可能不是很具效率 (如: 擴增 N 筆資料 所需的時間複雜度為 O(N) )，但是在對後續操作中能提升其計算效率中，從總體的角度來看時間複雜度反而是有所下降 (插入/刪除資料 Complexity 變為 O(1) )，即算法的每個操作的時間複雜度不一定相同，但在長時間內，每個操作的代價的平均值應該是穩定的。
平攤分析有三種方法:
- 聚攏法 (Aggregate method)
- 償還法 (Accounting Method)
- 位能法 (Potential Method)
