《圖說演算法-使用C#》要點摘錄 - 「運算思維與程式設計」
書名：《圖說演算法-使用C#》
作者：吳燦銘、胡昭民
所讀版本：博碩文化
運算思維
- 分析與拆解問題的能力
- 將問題「抽象化」與「具體化」
- 培養運算思維的四個面向
- 拆解
- 把複雜問題細分成許多小問題。
- 模式識別
- 在一堆資料中找出特徵或規則，用來將資料進行辨識與分類，做為決策的判斷。
- 歸納與抽象化
- 過濾以及忽略掉不必要的特徵，留下相關以及共同屬性，建立一個通用的問題以及怎麼解決的規則。
- 「抽象化」沒有固定的模式，每個人都有各自的拆解方式。
- 演算法
- 一種包含解決問題的每一個步驟和指示的計劃
- 拆解
演算法
- 「為了解決某一個工作或問題，所需要有限數目的機械性或重覆性指令與計算步驟」
- 演算法的條件：
- Input
- Output
- 明確性：每一個指令或步驟必須是簡潔明確而不含糊的
- 有限性：在有限步驟後一定會結束，不會無限Loop
- 有效性：步驟可行，使用者可以用紙筆計算求出答案
時間複雜度
- T(n) => 程式執行需時，n = 資料規模
- 一種「程序執行最壞情況需時」的概量。
- f(n) => 執行時間的成長率，需要取其最大者
- 常數可忽略不計
- 例子：T(n) = 3n^3 + 2n^2 + 5n
- c = 3 + 2 +5 = 10
- f(n) = n^3（最大）
- 3n^3 + 2n^2 + 5n = 10n^3
- 常數忽略不計，得出時間複雜度：O(n^3)
- 常見時間複雜度：
- O(1)：常數時間，執行時間為一個常數倍，數據量不影響執行時間
- O(n)：線性時間，執行時間與數據量等比上升
- O(log2n)：次線性時間，執行時間成長速度比常數時間快，比線性時間慢
- O(n^2)：平方時間，執行時間為數據量增長的二次方
- O(n^3)：立方時間，執行時間為數據量增長的三次方
- O(2^n)：指數時間，執行時間為2 * { 數據量增長 }次方，最慢時間複雜度
- O(nlog2n)：線性乘對數時間，執行時間成長速度比線性快，比平方時間慢
- 當n >= 16，優劣關係如下：
- O(1) < O(log2n) < O(n) < O(nlog2n) < O(n^2) < O(n^3) < O(2^n)
程式設計邏輯
- 結構化程序設計
- 「由下而上法」：從程式最容易的部分先編寫，再逐步擴大
- 「由上而下法」：將整個程式需求由大到小、從上而下分解成不同較小的「模組」
- 三種控制流程
- 循序結構（逐步執行）
- 選擇結構（條件判斷）
- 重複結構（迴圈）
- 面向對象程序設計（OOP）
- 認定每一個物件是一個獨立的個體，而每個獨立個體有其特定之功能及特性，而我們無需去理解這些特定功能如何達成這個目標的過程，僅需將需求告訴這個獨立個體。
- OOP的設計重點：
- 可讀性
- 複用性
- 延伸性
- OOP的特性：
- 封裝
- 對物件的狀態和行為進行「抽象化」，變成一個「模型」
- 「抽象化」：
- 將代表事物的資料隱藏起來，並定義「方法」作為操作這些資料的接口
- 使用者只能接觸到方法，而無法直接使用資料
- 時效性因而比起結構化程序設計而言大打折扣
- 繼承
- 允許了程式碼的重複使用
- 繼承是一種「複製」的動作，它子類將所參照的父類內的所有成員，完整地寫入子類中，然後還可以在子類上添加更多的資料和方法或修改從父類「繼承」過來的方法
- 多態
- 可先聲明一個父類，然後再將其轉型成繼承了該父類的不同子類
- 也可以呼叫父類中的函數，基於其子類各自的對該函數的覆寫，從而得到不同的結果。
- 封裝
- OOP的其他元素
- 物件（Object）
- 包括了：
- 資料
- 運算
- 具有：
- 狀態
- 行為
- 識別
- 包括了：
- 類別：具有相同結構及行為的物件集合，是許多物件共同特徵的描述或物件的抽象化
- 類別中的一個物件可被稱為「該類別的一個實例」
- 屬性：物件的基本特徵和性質
- 方法：物件的動作與行為
- 物件（Object）