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
查看全部
你可能也想看
創作者要怎麼好好休息 + 避免工作過量？《黑貓創作報#4》午安，最近累不累？
這篇不是虛假的關心。而是《黑貓創作報》發行以來可能最重要的一篇。
是的，我們這篇講怎麼補充能量，也就是怎麼休息。
2024-06-29
蕭氏人肉演算 ➔ 2023 Oct. 1通常我們都會用 Spotlight 來搜尋 Mac 裡的檔案，但有些時候這傢伙搜出來的結果也太多了！它把所有相關字詞的檔案、文件、圖片、郵件、應用程式都列給你看，深怕你不知道要找什麼一樣，結果就導致你得花更多時間在篩選上…。
2023-11-29
【1-3.2】用IPA標示「阿依烏欸喔」──元音組合與韻母這個系列的文章希望讓大家能夠學習一些語言學的概念，並且利用它們更有效率地學習各種語言。在語音篇的部分，想讓大家透過學習IPA字母，更好去掌握不同語言的發音訣竅。
2023-09-27
蕭氏人肉演算 ➔ 2023 Sep. 1a spirit that looks exactly like a living person, or someone who looks exactly like someone else but who is not related to that person
2023-09-03
蕭氏人肉演算 ➔ 2023 Aug. 1你今天「暈船」了嗎？在現今網路發達的世代，許多詞彙從網路族群的對話中延伸，開始流行起來。近年來，在網路各種論壇的感情版上，我們總可以看到「暈船」一詞，根據《KEYPO大數據關鍵引擎》顯示，近一年「暈船」這個網路用語聲量有3,789筆，這龐大的數據不禁使人疑惑，究竟什麼是暈船？
原文網址: 你暈船了嗎
2023-09-03
蕭氏人肉演算 ➔ 2023 Jul. 1第34屆金曲獎頒獎典禮將於7月1日（六）於台北小巨蛋舉行盛大舉行，入圍名單於5月16日（二）下午1點公布，今年典禮主持人將由韋禮安獨挑大樑，陳明珠、黃偉晉則擔任金曲獎星光大道主持人，超趣味組合讓眾人期待值拉好拉滿！
2023-07-02
2023-06-26
蕭氏人肉演算 ➔ 2023 May. 1PTT 常見的熱門文章中，有一類型就是在探討臺灣到底算不是算是「先進國家／已開發國家」，還是只算一個「後進國家／開發中國家」。
2023-05-06
1-11動手做一個屬於你的複利計算表(含複利程式範例與影片)本文章的複利程式展示影片:
從前一篇的文章，我們知道了透過複利可以創造財富，萬丈高樓始於平地起，但是應該要怎麼執行呢?對於許多投資理財新手來說，只知道複利很厲害，但卻感到很抽象，到底應該要怎麼設計自己的複利遊戲?才能讓自己看得到未來的財富成長之路呢?
在這篇會利用一個簡單的複利表範例，讓小白貓們了
2021-10-13
1 信仰是證據的免疫力──《信仰不是事實：為什麼科學與宗教不相容》大要 2019D1科學與宗教不相容。信仰是證據的免疫力，再確鑿的證據都可以忽視、否定。宗教以感情的交托代替證據的需求。要叫人相信科學，不但要有「事實」上的教育，而且要有「信仰」上的反教育。從民意調查可見，科學家、無神論者批評的是主流教義，打的不是稻草人。科學家信徒少，是研究科學叫人不信，而不是不信的人做了科學家。
2019-06-26
Facebook演算法下所產生的機會｜小編開講讓網友讚到嫑嫑的65個經營社群心法#1Facebook對網際網路市場最大的貢獻，就是讓使用者付費變成理所當然的事－－－推書的一千種方法
2019-01-29