Day 8 - 基礎計概 & 演算法

大學時修計概沒學好，現在慢慢補回來。基本上就是自己整理的筆記貼上來，完全零相關知識來看這篇應該有些部分難懂，不過我都有貼參考資料，有興趣可以連去看看。

程式語言基礎概念

所謂程式語言就是寫給電腦看懂的語言，把要做的事情拆解成一個個步驟，就是寫程式的概念；電腦（或其他裝置）會根據輸入的 code 一條條解讀並行動。

進位制度 Positional notation

常用進位制

• 十進位 Decimal (簡寫 dec)
• 二進位 Binary
• 八進位 Octal (簡寫 oct)
• 十六進位 Hexadecimal (簡寫 hex)

電腦裡的色碼表示

色碼是十六進位表示法，電腦裡的三原色：紅（Red）、綠（Green）、藍（Blue），每個顏色又細分成 256 個數值（0 到 255 共 256 個數字）。

範例

若 R: 255, G: 255, B: 0
那就是紅色 + 綠色，也就是黃色

經過十六進位轉換後結果
R: FF , G: FF, B: 00，所以色碼是 #FFFF00。

利用線上工具截的圖

二進位 Binary

二進位的 1010 = 2^3 + 2^1 轉換成十進位就是 10

十進位的 56 = 2^5 + 2^4 + 2^3 轉換成二進位 111000

56（十進位）轉換成 111000（二進位）的思路：

1. 56 和 2 的哪個次方最接近？答 2^5 = 32
2. 56 減去 32 剩下 24
3. 對 24 重複 Step 1. & 2. 的處理方式...
4. 最後可知 56 = 2^5 + 2^4 + 2^3
5. 再寫得更仔細 56 = 1 * 2^5 + 1 * 2^4 + 1 * 2^3 + 0 * 2^2 + 0 * 2^1 + 0 * 2^0
6. 所以換到二進位 111000

其他練習

27 = 2^4 + 2^3 + 2^1 + 2^0 -> 11011
32 = 2^5 -> 100000
100 = 2^6 + 2^5 + 2^2 -> 1100100

二位元負數

對應正數按 位元取反再加 1，這樣做的好處是正數負數相加可得到 0。

舉例

0   1   1   1   1   1   1   1   =   127
0   0   0   0   0   0   1   0   =   2
0   0   0   0   0   0   0   1   =   1
0   0   0   0   0   0   0   0   =   0
1   1   1   1   1   1   1   1   =   −1
1   1   1   1   1   1   1   0   =   −2
1   0   0   0   0   0   0   1   =   −127
1   0   0   0   0   0   0   0   =   −128

浮點數

[C&C++] 浮點數精準度 (Floating-Point Precision)

使用浮點數最最基本的觀念

儲存空間單位

電腦的最小單位為 Bit （位元）

• 1 Byte = 8 Bits，Byte 又稱位元組
• 1 Kilobyte (KB) = 1024 Bytes
• 1 Megabyte (MB) = 1024 KB
• 1 Gigabyte (GB) = 1024 MB
• 1 Terabyte (TB) = 1024 GB
• 1 Petabyte (PB) = 1024 TB
• 1 Exabyte (EB) = 1024 PB
• 1 Zettabyte (ZB) = 1024 EB
• 1 Yottabyte (YB) = 1024 ZB

參考：
文件大小

電腦語言

重要觀念：電腦只看得懂機器語言（二進位的 0101...）

組合語言（assembly language）：接近電腦底層的組合語言，一個指令只做一兩件事情，只翻譯成 機器語言。

編譯器（compiler）：一種電腦程式，它會將某種程式語言寫成的原始碼（原始語言）轉換成另一種程式語言（目標語言）。可以想成是翻譯器，把人類容易看懂的內容轉換成電腦能讀懂的內容。

逆向工程：透過反組譯（disassemble）將機器語言轉換為組合語言，與編譯器所做的事情相反。用這個方法可以知道電腦程式的內容，甚至可以修改其中內容而變成破解版的程式。

演算法 Algorithm

演算法簡單來說就是解決問題的方法

輸入 + 演算法 = 輸出

以 複雜度 來衡量演算法的好壞，分兩類

• 時間複雜度（Time Complexity）：演算法需要消耗的時間資源。
• 空間複雜度（Space Complexity）：演算法需要消耗的空間資源。

參考：
圖形動畫講解演算法 VisuAlgo
基礎電腦科學：演算法概要
【演算法】時間複雜度與空間複雜度Time & Space Complexity

時間複雜度（Time Complexity）

通常使用 Big O notation 大 O 符號 來表示時間複雜度。

圖源

參考：
Complexity：Asymptotic Notation(漸進符號)

搜尋法

二分搜尋法：每次都切一半來找目。

排序演算法（Sorting algorithm）

選擇排序法（Selection sort）

1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
2. 再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。
3. 以此類推，直到所有元素均排序完畢。

泡沫排序法（Bubble sort）

1. 從序列第一個元素開始往後比較。
2. 若後面的比現在挑中的還大，那就把挑中的元素換成該數繼續往後比；若後面的比現在挑中的還小，那就把兩者順序對調然後再和下一個數字比。
3. 重複以上步驟直到排序結束。

插入排序法（Insertion sort）

和撲克牌排序方式一樣。

合併排序

1. 將陣列分割直到只有一個元素。
2. 開始兩兩合併，每次合併同時進行排序，合併出排序過的陣列。
3. 重複 2 的動作直接全部合併完成。

快速排序

1. 挑選基準值：從數列中挑出一個元素，稱為「基準」（pivot），
2. 分割：重新排序數列，所有比基準值小的元素擺放在基準前面，所有比基準值大的元素擺在基準後面（與基準值相等的數可以到任何一邊）。在這個分割結束之後，對基準值的排序就已經完成，
3. 遞迴排序子序列：遞迴地將小於基準值元素的子序列和大於基準值元素的子序列排序。

參考：
【演算法】排序演算法 Sorting Algorithm