[toc]

# Software Development Basic
一個程式語言，都會有幾種最基礎的資料形態。就像是所有分子都由元素週期表上的元素所組成，資料形別代表了程式中的所有輸入和輸出，以及中間被運算的所有單元。一個程式語言通常有以下幾種基本的資料型別，
- int
- float
- char

在C語言中，還有其他資料型別如下，
- char
- bool
- double

**Abstract Data Type (ADT)**
而在這之上，也有可由使用者自由定義的struct，struct可以包含上述所有資料型別的排列組合，甚至是另一個struct。舉例來說，當我們想知道一個人的身分，可以從基礎的身高、體重、身分證字號、年紀等等來觀察，上述這些便是基礎的資料型別，而**人**便是複合式的資料型別。透過這些資料型別的排列組合，我們可以構築出生活中所看到各式各樣的軟體。

# 資料結構
在談資料結構和演算法之前，我們要先對一個軟體的成分有所了解。每個軟體存在的意義都是將輸入的資料轉換成輸出的結構。其實所有程式都在做一件相同的是，如何讀取資料、操控資料，分類資料，而如何巧妙地運用不同的資料結構和演算法來解決一個問題，實現最低的運算時間和最少的運算資源，會是接下來的重點。舉生活上最常見的例子就是email。每個人每天都有成千上萬封email，我們要如何找尋對我們來說有用的信件呢？其中一個作法是透過時間來排序，將越新的信件置於越上面，這就是排列資料的一種方式。另外一個是把信添加到重要郵件，或使用Filter濾除不要的信件，這些都用到了資料結構的概念，也就是資料的操控和排序，最終讓使用者接收到，資料結構的本質就是一個資料的集合。而唯一的區別就是，這些資料要以怎樣的形式排列，要用怎樣的排序方式，才更適用在對的地方。

# 演算法
Algorithm，中文又稱演算法，是一種用來解決問題的方法。舉例來說，如果我能從今天的天氣狀況，得到明天的股市漲跌，那這就是一種演算法。演算法類似數學之中的函數，給予適當的輸入，便會給你想要的輸出。

演算法通常不會由通常不會由簡單的幾行程式碼所組成，而是會由一個數千行甚至數萬行的程式碼協作而成。面對如此大的程式，我們很難一口氣開發完畢。就像是一台車，會有引擎、方向盤、馬達、輪胎、煞車、儀錶板、汽缸 等等的零件組合而成，程式開發也一樣，我們也要透過大量的零件組合而成。建立在這個基礎之上，我們會有兩種設計理念:
- Bottom Up
Bottom Up的意思就是透過現有的零組件，去組合出想要的產品。舉例來說，我組一張桌子，我去找市面上有合適長度的柱子，足夠寬的木板，和夠長的螺絲，組合起來之後得到一張堪用的桌子。用IC Design的話來說，這種開發模式就像是cell-based，基於現有零件組合出產品。

- Top Down
Top Down的意思就是將產品拆解成幾個部分，並依序實現。同樣舉桌子的例子，我先設計出桌子的長寬高，接著我依序量出木板、柱子、螺絲要多長，並送去工廠客製化的實現出來。用IC Design的話來說，這種開發模式就像是ASIC，從頭開始設計出一個客製化的產品。由於客製化的緣故，Top Down設計出的產品往往有比較好的效能。

兩者的區別就是
**Bottom Up**的**開發週期短但品質較差**
**Top Down**的**開發時間長但品質較好**

演算法的本質是一種方法，因此不存在語言方面的限制。一個演算法可以用C/C++，也可以用Python或其他程式語言來表示，當然，使用自然語言也可以，比如說中文或英文。一個演算法需要具備下列幾個條件，
1. Input : 一個演算法會有0個或以上的輸入。
2. Output : 至少一個值會被輸出。
3. Definiteness : 每個步驟必須清楚且不含糊。
4. Finiteness : 一個演算法必須由有限的步驟所組成。
5. Effectiveness : 每個指令必須足夠簡單，必須是明確且可執行的。

程式(Program)和演算法(Algorithm)一個最主要的區別就是，程式可以是Infinite。試想一下我們平使用的手機、伺服器等等，通常都是不斷地執行，並沒有結束的情況，然而演算法並不是如此，演算法是**有限的**。

# 複雜度
針對一個問題，我們往往可以提出不只一種解法。那這就代表了，每種解法都一樣嗎？不對的，解法和解法之間，也同樣存在著優劣之分。那我們該如何去比較不同解法之間的優劣呢？答案就是複雜度。

## Big-O Notation
Big-O 表示一個演算法所耗費的資源，這邊的資源有**時間**跟**空間**兩種。時間指的是運算所耗費的時間。空間指的是運算所佔用的記憶體資源。針對一個演算法，我們習慣用 Worst Case 去描述他的效能，當**輸入N筆資料**，我們會需要多少資源去計算輸出，這個資源量我們會用 O(N) 去表示。其中當 N 很大的時候，我們更在意其數量級，而非低次項的係數或常數等等，因此我們通常保留 Dominant 的項。值得注意的是，一個演算法根據情況不同，Best Case跟Worst Case還有Average Case的情況會有需要不同的步驟與運算時間，O(N)是代表Worst Case所需的時間，這也相較於另外兩種情況來說更重要。

舉例來說，我們用 S(N) 代表一個演算法實際耗費的資源。
$S(N)=2^N+N^2+1$，當 N 很大，$N^2$ 和 $1$ 貢獻的數目近乎可忽略，因此我們說 $O(N)=2^N$

最後，O(N)的量級從大到小(比較粗略的分類)依序是，
$O(N^N)>O(N!)>O(2^N)>O(N^k)>O(N\log N)>O(N)>O(\log N)>O(1)$
其中 $O(1)$ 又會被我們稱為 Fixed Time/Space Requirement，他代表了不論輸入的資料數量為何，演算法所需的**時間**、**硬體**資源是固定的。

而耗費的資源往往是越少越好，因此更靠右側的演算法是更為優異的演算法。

有興趣的人可以再深入了解 Big-O Notation 在數學上更精準的定義。
https://medium.com/@ralph-tech/%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B-%E6%BC%94%E7%AE%97%E6%B3%95%E5%AD%B8%E7%BF%92%E7%AD%86%E8%A8%98-%E8%A4%87%E9%9B%9C%E5%BA%A6-complexity-%E6%BC%B8%E8%BF%91%E7%AC%A6%E8%99%9F-asymptotic-notation-77f2c0899c8b

簡而言之，
- Big-O :
對於所有的 n≥n₀，0≤f(n)≤c·g(n)，也就是只要在 n₀ 以上，f(n) 永遠比 c·g(n) 小，c·g(n) 表示 f(n) 的上界（upper bound），此時 f(n) 被定義為 O(g(n))，這個 O(g(n)) 就是「Big O」
- Big-Ω :
f(n)=Ω(g(n))，若且唯若存在正實數 c、正實數 n₀，對於所有的 n≥n₀，可滿足 0 ≤ c·g(n) ≤ f(n)
- Big-θ:
f(n)=θ(g(n))，若且唯若存在正實數 c₁、正實數 c₂、正實數 n₀，對於所有的 n≥n₀，可滿足 0 ≤ c₁·g(n) ≤ f(n) ≤ c₂·g(n)。

Big-θ不一定存在於所有演算法之中，僅在上面Big-O和Big-Ω為相同複雜度時成立。由於無法穩定的表示所有複雜度，因此我們多採用Big-O的最小者來做為複雜度的表示。


### 時間複雜度(Time Complexity)
時間複雜度指的是，運算所花費的時間越短，則時間複雜度越好。這個時間，可以用system clock計算的時間差來表示。第二種方法是用運算數量來表示。通常用運算數量更能精準表達一個演算法的效率，因為實際運算時間容易隨著硬體規格不同，出現更好的硬體用較爛的演算法卻比爛硬體用好演算法的時間更快。(金錢的威力?)

如下面程式所示，我們可以使用count來計算程式總共運算的次數

float sum(float list[], int n){
    float tempsum = 0; count++;
    int i ; 
    for (i = 0; i<n; i++){
        count++;
        tempsum += list[n]; count++;
    }
     count++; /
     count++; /
}
 
// Final Count = 2n+3

而使用遞迴的程式碼如下

float rsum(float list[], int n)
{
    count++;
    if(n) {
        count++;
        return rsum(list, n-1) + list[n-1];
    }
    count++;
    return list[0];
}

// Final Count = 2n+2

從上面可以看到，使用遞迴的算法所執行的步驟比較短(2n+2 < 2n+3)，但事實上，每種指令所需要執行的時間並不相同，因此，這只是種參考的依據。

### 空間複雜度(Space Complexity)
空間複雜指的是，運算所使用的記憶體(硬體資源)越少，則空間複雜度越好。

讓我們看到下面這段程式碼，其運算量並不會改變，所需的硬體資源為 Fixed Space

float abc(float a, float b, float c)
{
    return a+b+b*c + (a+b-c)/a+b + 4.00;
}

再看到下面這段將陣列所有元素相加的程式碼，

float sum(float list[], float n)
{
    float tempsum = 0;
    int i;
    for(i=0; i<n; i++)
        tempsum += list[i];
    return tempsum;
}

這段程式碼當中，如果是 Pascal 之類的程式語言，會將整個陣列的內容複製到函式內，因此空間複雜度為 O(n)=N。而如果是 C 語言，並不會複製陣列元素，而是直接到陣列所在的記憶體查找值，因此
對C語言來說，並不需要額外的硬體資源，O(n)=C。

接下來，讓我們看到遞迴的狀況，

float rsum(float list[], int n)
{
    if(n) return rsum(list, n-1) + list[n-1];
    return 0;
}

在上述程式碼中，每一次呼叫遞迴，我們就需要紀錄一個float(指標，8 bytes)，一個int(4 bytes)，一個回傳位址(位址，等同指標大小，8 bytes)。加總起來為 20 bytes。考慮 n 為 1000，整個 recursive 會被呼叫 1000 次，總共會需要 20000 bytes。在這個情況下，其空間複雜度為O(n)=N。

----
當我們使用不同演算法去解決同一個問題的時候，會出現不同時間複雜度和空間複雜度的比較。因此有時候不會有**最好**的算法，通常只會有**最適合**的算法。

# 函數指針
函數指針提供我們使用類似動態記憶體的方式去定義函數。
我們對比一下有無使用函數指針的區別，

| 特性 | 無函數指針 | 有函數指針 |
| -------- | -------- | -------- |
| 靈活性 | 每個處理邏輯需要獨立寫函數和調用邏輯。 | 可通過函數指針動態選擇處理邏輯，主程式不需改動。 |
| 代碼重用性 | 重複編寫迴圈邏輯，處理函數多時會導致代碼膨脹。 | 通用 processArray 處理邏輯只寫一次即可重用。 |
| 擴展性 | 新增邏輯需要修改主程式並添加新的函數。 |新增邏輯只需定義新的函數並作為函數指針傳入即可。|
| 可讀性 | 主程式中重複代碼較多，處理邏輯難以分離，閱讀困難。 | 主程式簡潔，處理邏輯分離，函數名稱表意清晰，閱讀友好。 |
| 維護成本 | 處理邏輯分散，代碼重複多，修改或調試時容易出錯。 | 處理邏輯集中，代碼清晰，修改和調試成本低。
|

這邊給一個例子，

**無函數指針:**

#include <stdio.h>

// 處理數組：將每個元素平方
void squareArray(int *array, int size) {
    for (int i = 0; i < size; i++) {
        array[i] = array[i] * array[i];
    }
}

// 處理數組：將每個元素乘以 2
void doubleArray(int *array, int size) {
    for (int i = 0; i < size; i++) {
        array[i] = array[i] * 2;
    }
}

int main() {
    int array[] = {1, 2, 3, 4, 5};
    int size = sizeof(array) / sizeof(array[0]);

    printf("Original array:\n");
    for (int i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");

    // 使用平方邏輯處理數組
    squareArray(array, size);
    printf("Array after squaring elements:\n");
    for (int i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");

    // 使用雙倍邏輯處理數組
    doubleArray(array, size);
    printf("Array after doubling elements:\n");
    for (int i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");

    return 0;
}

**函數指針:**

#include <stdio.h>

// 通用處理函數，接受一個數組及一個處理函數指針
void processArray(int *array, int size, void (*processFunc)(int *)) {
    for (int i = 0; i < size; i++) {
        processFunc(&array[i]);
    }
}

// 處理函數 1：將數組的每個元素平方
void square(int *num) {
    *num = (*num) * (*num);
}

// 處理函數 2：將數組的每個元素乘以 2
void doubleValue(int *num) {
    *num = (*num) * 2;
}

int main() {
    int array[] = {1, 2, 3, 4, 5};
    int size = sizeof(array) / sizeof(array[0]);

    printf("Original array:\n");
    for (int i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");

    // 使用平方邏輯處理數組
    processArray(array, size, square);
    printf("Array after squaring elements:\n");
    for (int i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");

    // 使用雙倍邏輯處理數組
    processArray(array, size, doubleValue);
    printf("Array after doubling elements:\n");
    for (int i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");

    return 0;
}