書名:《圖說演算法-使用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)
包括了:
資料
運算
具有:
狀態
行為
識別
類別:具有相同結構及行為的物件集合,是許多物件共同特徵的描述或物件的抽象化
類別中的一個物件可被稱為「該類別的一個實例」
屬性:物件的基本特徵和性質
方法:物件的動作與行為