# 【學習筆記】圖說演算法(JavaScript) - 大話運算思維與程式設計

> 以下所有內容皆取自書本中，若書本中講解得過於模糊，會補充一些網路上的資料。

本節心智圖：


(文字過小可以右鍵 - 在新分頁中開啟圖片)

---

## 運算思維

1. 任何只要牽涉到「**解決問題**」的議題都可以套用「**運算思維**」來解決。
2. 運算思維即利用電腦的邏輯來解決問題的思維，就是一種能夠將問題「**抽象化**」、「**具體化**」的能力。
3. 規劃路線後按照計畫出發，這種計畫與考量過程就是運算思維。按照計畫逐步執行就是一種演算法。
4. Google 開發的一套運算思維課程(Computational Thinking for Educators)提到培養運算思維的四個面向：**拆解、模式識別、歸納與抽象、演算法**。

## 運算思維的四個面向

1. **拆解(Decomposition)**：將問題拆分成多個小問題後各個擊破。
2. **模式識別(Pattern Recognition)**：
- 一個複雜問題分解後，多個小問題中可能會有共有的屬性以及相似之處，這些屬性就稱之為「**模式**」。
- 模式識別指的是在一堆資料中找出特徵或問題中的相似之處。
- 用來將資料進行辨識與分類，並找出規律性，才能作為快速決策判斷。
4. **歸納與抽象(Pattern generalization and abstraction)**：過濾以及忽略掉不必要的特徵，使我們可以針對重要特徵將問題具體化，進而建立模型。
- 建立模型的目的在於希望能從原始特徵數據集合中學習出問題的結構與本質。
- 抽象化沒有固定的模式，隨著需要或實際狀況而有不同。
- EX: 車商業務員：輪子、引擎、方向盤、煞車、底盤
5. **演算法(Algorithm)**：為了解決某一個工作或問題，所需要有限數目的機械性或重複性指令與計算步驟。
- 人類利用電腦解決問題的技巧之一，也是程式設計領域最重要的關鍵，常被使用為設計電腦程式的第一步。

例如輾轉相除法演算法如下：

    let n = 123;
    let m = 456;
    let temp = 0;

    if (n < m) {
        temp = n;
        n = m;
        m = temp;		
    }

    while(m != 0) {
        temp = n % m;
        n = m;
        m = temp;
    }

    console.log('最大公因數:', n);

## 生活中到處都是演算法

流程圖也是一種相當通用的演算法表示法，必須使用某些圖形符號。

### 演算法的五項條件

1. 輸入：0 個或多個輸入資料，這些輸入必須有清楚的描述與定義。
2. 輸出：至少會有一個輸出結果，不能沒有輸出結果。
3. 有限：每一個指令或步驟必須是簡潔明確而不含糊的。
4. 明確：在有限步驟後一定會結束，不會產生無窮迴圈。
5. 有效：步驟清楚且可行，能讓使用者用紙筆計算而求出答案。

演算法與程式最大的不同之處在於，程式不一定要滿足局限性的要求，如作業系統或機器上的運作程式，除非當機，否則永遠在等待迴路，這也違反了演算法五大原則之一的「**有限性**」。

### 時間複雜度O(f(n))

演算法的時間複雜度(Time Complexity)是一個函數，它定性描述該演算法的執行時間。

- 大 O 符號：用來描述演算法在輸入 n 個東西時，所需時間與 n 的關係。
- 在 n 非常大時，好的演算法設計可以省下非常多時間。
- 演算法的速度不是以秒計算，而是以步驟次數，但也不是真正的執行次數，而是一個概略的量度層級。
- 實務上，我們只會紀錄最高次方的那一項，並忽略其所有的係數。

以上四點摘自[從時間複雜度認識演算法](https://medium.com/appworks-school/%E5%88%9D%E5%AD%B8%E8%80%85%E5%AD%B8%E6%BC%94%E7%AE%97%E6%B3%95-%E5%BE%9E%E6%99%82%E9%96%93%E8%A4%87%E9%9B%9C%E5%BA%A6%E8%AA%8D%E8%AD%98%E5%B8%B8%E8%A6%8B%E6%BC%94%E7%AE%97%E6%B3%95-%E4%B8%80-b46fece65ba5)，因為書本裡面寫的太差。

常見的 Big-oh 有下列幾種：



> 書本對時間複雜度這塊基本可以說是說了又好像沒說，建議可以閱讀：[[演算法]Big O and Time Complexity](https://medium.com/@yunyubee/%E6%BC%94%E7%AE%97%E6%B3%95-big-o-and-time-complexity-65f2dfafe9d1)