1. 演算法與運算
更新於 發佈於 閱讀時間約 1 分鐘
Lecture 1: Algorithms and Computation
課程目的
- 解決電腦上遇到的問題
- 證明正確性
- 探討效率
並且很著重溝通，說服別人你做的事是正確且有效率的。
何謂電腦問題
你有輸入，需要輸出。
A輸入的正確解答是BCD輸出，解決這個問題的方法就是電腦問題。
演算法
給一個輸入，軟體或方法給一個「正確」輸出，就是演算法。
範例：學生生日相同與否演算法
方法一
記錄所有學生的生日，每次紀錄新資料時，比對已記錄資料，若有相同生日，回傳「是」。
時間複雜度：O(n)
空間複雜度：O(n)
正確性
歸納法證明
若前K名學生有人的生日一樣，在問第K+1名學生之前回傳「是」。
若K=0，則回傳「否」。
則K=K'時，會出現兩種情況：
- K’已回傳「是」，有相同解。
- 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可以操作這些資料。
留言0
查看全部
你可能也想看
Google News 追蹤
嘿，大家新年快樂~ 新年大家都在做什麼呢？
跨年夜的我趕工製作某個外包設計案，在工作告一段落時趕上倒數。
然後和兩個小孩過了一個忙亂的元旦。在深夜時刻，看到朋友傳來的解籤網站，興致勃勃熬夜體驗了一下，覺得非常好玩，或許有人玩過了，但還是想寫上來分享紀錄一下~
《從 0 到 1》探討開創獨占新事業的重要，但吳軍博士指出，真正的挑戰在於從科學到技術、再到商業成功的完整過程，而非僅僅是一個好點子。本文透過過蘋果、微軟與 Google 的案例，思考使用者體驗與持續改進，以及宏大的變革目標（MTP）如何引導創業者走向成功。
咕嚕（Gollum）原名史麥戈（Sméagol），是英國作家J·R·R·托爾金小說內的虛構角色，在小說《哈比人歷險記》裡首次登場，並在該作家的續作《魔戒》中擔任其中一名主要角色。
嘿，大家新年快樂~ 新年大家都在做什麼呢？
跨年夜的我趕工製作某個外包設計案，在工作告一段落時趕上倒數。
然後和兩個小孩過了一個忙亂的元旦。在深夜時刻，看到朋友傳來的解籤網站，興致勃勃熬夜體驗了一下，覺得非常好玩，或許有人玩過了，但還是想寫上來分享紀錄一下~
《從 0 到 1》探討開創獨占新事業的重要，但吳軍博士指出，真正的挑戰在於從科學到技術、再到商業成功的完整過程，而非僅僅是一個好點子。本文透過過蘋果、微軟與 Google 的案例，思考使用者體驗與持續改進，以及宏大的變革目標（MTP）如何引導創業者走向成功。
咕嚕（Gollum）原名史麥戈（Sméagol），是英國作家J·R·R·托爾金小說內的虛構角色，在小說《哈比人歷險記》裡首次登場，並在該作家的續作《魔戒》中擔任其中一名主要角色。