【 第四章 】

撲克牌教我演算法

對應的課綱主題:演算法

本章嘗試從 「程式」 到 「演算法」,讓大家試著去體驗 「運算思維」。前面說過,運算思維就是以電腦的執行邏輯脈絡來思考問題並解決問題!運算思維的訓練有很多好處,他可鍛鍊我們以清晰的步驟來處理解決生活周遭的問題與困難。當我們能清楚的描述步驟後,電腦就可以為我們代勞解決問題。你我可以不再是單純運用人力解決問題,或者是使用現成的軟體或演算法做既定的事情。當你精熟於運算思維時,你可以使用程式語言撰寫自己的應用程式,利用演算法來解決問題並同時享受創作的樂趣。電腦就如同一塊畫布一般有著無限的可能,而運算思維就是電腦資訊科學最好的入門磚,這也是我們想帶給你的樂

趣所在!⋯⋯

大符號O(Big-O)


大O符號(英語:Big O notation),又稱為漸進符號,是用於描述函式漸近行為的數學符號。更確切地說,它是用另一個(通常更簡單的)函式來描述一個函式數量級的漸近上界。在數學中,它一般用來刻畫被截斷的無窮級數尤其是漸近級數的剩餘項;在電腦科學中,它在分析演算法複雜性的方面非常有用。 大O符號是由德國數論學家保羅·巴赫曼在其1892年的著作《解析數論》(Analytische Zahlentheorie)首先引入的。而這個記號則是在另一位德國數論學家艾德蒙·朗道的著作中才推廣的,因此它有時又稱為朗道符號(Landau symbols)。代表「order of ...」(……階)的大O,最初是一個大寫希臘字母「Ο」(omicron),現今用的是大寫拉丁字母「O」。 WiKi連結
網路資源
1. AppWorks School: 初學者學演算法|談什麼是演算法和時間複雜度




空間複雜度(Space Complexity)


演算法的空間複雜度是指演算法需要消耗的空間資源。其計算和表示方法與時間複雜度類似,一般都用複雜度的漸近性來表示。同時間複雜度相比,空間複雜度的分析要簡單得多。 WiKi連結
網路資源 1. ITREAD01: 演算法的時間與空間複雜度(一看就懂) 2. 每日頭條: 時間複雜度、空間複雜度,如何「不複雜」地學? 3. MBAlib: 空間複雜度




時間複雜度(Time complexity)


在電腦科學中,演算法的時間複雜度(Time complexity)是一個函式,它定性描述該演算法的執行時間。這是一個代表演算法輸入值的字串的長度的函式。時間複雜度常用大O符號表述,不包括這個函式的低階項和首項係數。使用這種方式時,時間複雜度可被稱為是漸近的,亦即考察輸入值大小趨近無窮時的情況。例如,如果一個演算法對於任何大小為 n (必須比 n0 大)的輸入,它至多需要 5n3 + 3n 的時間執行完畢,那麼它的漸近時間複雜度是 O(n3)。 為了計算時間複雜度,我們通常會估計演算法的操作單元數量,每個單元執行的時間都是相同的。因此,總運行時間和演算法的操作單元數量最多相差一個常數係數。 WiKi連結
網路資源 1. IT邦幫忙 : 如何衡量程式的效率?——論時間複雜度(Time Complexity) 2. AppWorks School: 初學者學演算法|從時間複雜度認識常見演算法 3. YC Note: 輕鬆談演算法的複雜度分界:什麼是P, NP, NP-Complete, NP-Hard問題




分析機(Analytical Engine)


分析機是由英國數學家查爾斯·巴貝奇設計的一種機械式通用計算機。從1837年首次提出這種機器的設計,一直到他去世的1871年,由於種種原因,這種機器並沒有被真正地製造出來。但它本身的設計邏輯卻十分先進,是大約100年後電子通用計算機的先驅。 WiKi連結
網路資源 1. 癮科技: 癮科學:查爾斯.巴貝奇的差分機與分析機 2. 風傳媒: 人類第一台電腦-巴貝奇的分析機 3. 泛科技: 巴貝奇發表差分機:生錯時代的第一部電腦




對數(Logarithm)


在數學中,對數是冪運算的逆運算。用日常語言說,即「以3為底81的對數是4」。 WiKi連結
網路資源 1. academy: 數學:對數的由來 2. 科學online: 對數




遞迴(Recursion)


在數學與電腦科學中,是指在函數的定義中使用函數自身的方法。遞迴一詞還較常用於描述以自相似方法重複事物的過程。例如,當兩面鏡子相互之間近似平行時,鏡中巢狀的圖像是以無限遞迴的形式出現的。也可以理解為自我複製的過程。 WiKi連結
網路資源 1. 海洋大學 電機資訊學院 資訊工程學系 Lagoon: 遞迴 (recursive) 函式之設計 2. 程式前沿: 一文讀懂遞迴演算法




分而治(Divide-and-conquer algorithm)


在電腦科學中,分治法是建基於多項分支遞迴的一種很重要的演算法範式。字面上的解釋是「分而治之」,就是把一個複雜的問題分成兩個或更多的相同或相似的子問題,直到最後子問題可以簡單的直接求解,原問題的解即子問題的解的合併。 WiKi連結
網路資源 1. Startup 2.0 工程師創業手冊 – 高科技創業經驗分享: 創業公司管理 – 解決問題的方法,Divide and Conquer個個擊破 2. CSDN: 分治策略Divide and Conquer





合作廠商

聯絡我們:

Abbie Tseng 曾旭君小姐

Abbie@redhill.idv.tw