《圖說演算法-使用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)

        • 包括了:

          • 資料

          • 運算

        • 具有:

          • 狀態

          • 行為

          • 識別

      • 類別:具有相同結構及行為的物件集合,是許多物件共同特徵的描述或物件的抽象化

        • 類別中的一個物件可被稱為「該類別的一個實例」

      • 屬性:物件的基本特徵和性質

      • 方法:物件的動作與行為