1. 演算法與運算

Lecture 1: Algorithms and Computation

課程目的

• 解決電腦上遇到的問題
• 證明正確性
• 探討效率

並且很著重溝通，說服別人你做的事是正確且有效率的。

何謂電腦問題

你有輸入，需要輸出。

A輸入的正確解答是BCD輸出，解決這個問題的方法就是電腦問題。

演算法

給一個輸入，軟體或方法給一個「正確」輸出，就是演算法。

範例：學生生日相同與否演算法

方法一

記錄所有學生的生日，每次紀錄新資料時，比對已記錄資料，若有相同生日，回傳「是」。

時間複雜度：O(n)

空間複雜度：O(n)

正確性

歸納法證明

若前K名學生有人的生日一樣，在問第K+1名學生之前回傳「是」。

若K=0，則回傳「否」。

則K=K'時，會出現兩種情況：

1. K’已回傳「是」，有相同解。
2. K’沒有相同解，比較K’+1。

效率

衡量效率時需要顧慮電腦性能與輸入資料規模，所以不比較時間，而比較輸出答案所需的執行次數。

為此會需要用到「漸近分析」，會在之後被討論到。

預期演算法會隨著輸入大小改變輸出所需時間。

漸近符號（asymptotic notation）

大 O 符號（Big O notation）：最高上限

大 Ω 符號（Big Omega notation）：最低下限

大 θ 符號（Big Theta notation）：上下限之間的區間

計算模型

Word RAM

「Word」代表的是CPU可以處裡的資料量，RAM就是記憶體（Random access memory）。

現在的作業系統大多是64bits，以前是32bits。

32bits最多只能有2^32bytes的儲存空間，大約4GB。

64bits可以有2^64bytes，大約20EB，短時間內用不完就對了。

CPU

可以進行數字運算、邏輯判斷、Bitwise Operation

資料結構

前八堂課會討論資料結構，會討論儲存大資料的方法與怎麼讓CPU可以操作這些資料。