延續自昨天，今天要來探討分析解決問題方法的效率的方法！

程式好壞評估

這邊先請大家思考一下：要怎麼精準評估一個程式寫的好不好呢?

一般來說，一個程式

• 跑得快
• 記憶體用的少
• 正確率高不容易出錯

這樣我們會認為一個程式寫得很好
因此我們有三種指標來評估一個程式：時間成本、空間成本(記憶體消耗)、正確性

關於正確性的分析平常比較少機會用到，其實像是隨機化演算法因為內部流程中引入了隨機數，因此它必須仰賴一些機率的分析來證明其正確性；或者像深度學習中有所謂的啟發式演算法，就是當某問題（如下圍棋或一些類神經網路的優化問題等）的可能性實在太多太複雜，很難設計演算法求得最佳解時，人們就會基於一些直覺或是從自然界中發想出某種「策略」，來求得沒那麼好、卻也堪用的次佳解，像這樣的解答也需要被證明它「夠不夠好」

不過以下我們還是以時間、空間的評估為主；因為正確性的評估一般來說通常較少用到，而且也較為複雜。

時間成本、空間成本

那我們要怎麼精準評估一個程式的時間成本、空間成本呢?

其實最直覺的方法就是跑跑看就知道了嘛~但單純透過實際運行並不是一個可靠的方法。這是因為同一個程式在不同的硬體或環境中運行時，其效能會有所差異。就像同一個程式，在你的手機上跑和在超級電腦上跑，速度肯定差很大呀！

而且更重要的是，我們的目的是評估程式解決問題的「演算法」，而非特定的程式實現。同一個演算法在不同程式語言或系統環境下的表現可能會有所不同，甚至由不同的程式設計師實現時，也可能因為細微的實作差異而有不同的時間或空間成本。

因此，實際的執行時間和記憶體消耗並不適合作為評估解法效率的唯一標準。為了更客觀地評估解法的效率，電腦科學家通常會選擇通過統計解法的步驟數量和變數數量來評估時間和空間成本。

所謂的步驟就是指程式中在語法或語意上具有意義的單一片段(如：加減乘除、變數指派、存取/寫入記憶體、條件判斷等)，它的執行時間必須與輸入無關。這樣定義一來避免了剛剛提到的"因為外在環境因素而導致難以評估"的問題；二來因為程式中每個動作(存取、寫入記憶體、加減乘除等)若要細究它們的時間是一項大工程，而且這樣做很沒必要，因為老實說它們速度差異並沒有很大，因此「不管它們是黑貓、白貓，會捉老鼠就是貓」，把它們都歸類為「步驟」作為基本單位來分析是很棒的。

而變數數量就是程式中宣告的變數數量，如果是如陣列、結構等較為複雜的資料型別，或像 C++ STL 中那些如 vector、map 等，因為其實它們底層都還是一大堆變數按照某種規則組合在一起，因此必須算清楚它們所用的變數數量。

粗暴的步驟數統計

先看看下面的 C++ 片段：

int sum(int array[], int n) {
    int result = 0;
    for (int i = 0; i < n; ++i) {
        result += array[i];
    }
    return result;
}

這是一個簡單的對陣列加總的程式，我們將統計這個程式的步驟數量、變數數量來評估此演算法的好壞。

變數數量

首先變數數量好解決，就是這個程式為了解決陣列加總的問題迎合輸入，總共創建了幾個新變數呢?

    ...
    int result = 0;
    for (int i = 0; i < n; ++i)
    ...

很明顯不管 array 和 n 怎麼變，至多只有兩個新變數！所以若用函數 f(n) = x 表示對於輸入 n，該陣列加總的程式的變數數量為 x，則 f(x)=2，這是個常數函數表示變數數量與輸入無關。

步驟數量

那步驟數量呢？這部分會隨著輸入變化，因此我們假設輸入以下資料：

constexpr int n = 10;
int array[n] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

然後因為我懶得算XD，所以乾脆開一個新變數來記錄步驟數量：

int sum(int array[], int n) {
    int step = 0; // 紀錄步驟數量，不影響演算法流程
    int result = 0; ++step;
    ++step; // 計算 int i = 0 這一步驟
    for (int i = 0; ++step, i < n; ++i, ++step) {
        result += array[i]; ++step;
    }
    ++step; // 計算 return result 這一步驟
    cout << step << "\n";
    return result;
}

如上可以看到，我在每個「步驟」執行的地方跑一次 ++step 因此最後 step 的數值就會是該演算法的步驟數！

那我們的結果是：

34

不過想當然耳，在現實生活中我們不可能只用電腦處理 6 個數字的加法，實際遭遇的輸入一定會再更大一點的，因此現在我把輸入變成如下形式：

constexpr int n = 1000000;
int array[n];

我這邊僅僅是表示我輸入的陣列規模而已，因為陣列中的數值並不會影響步驟數，因此這邊沒有提到。有實驗精神的人也可以自己用 rand() 來填充陣列數值來實驗看看

此時的步驟數是：

3000004

...有沒有感受到一種說不上來的既視感
再多看看幾個例子：

輸入

constexpr int n = 100;
int array[n];

輸出

304

輸入

constexpr int n = 50;
int array[n];

輸出

154

發現了嗎？步驟數恰好等於輸入 n 的 3n + 4 。

寫成函數表示就是令函數 f(n) = x 表示對於輸入 n 時，此時的步驟數為 x，則 f(n) = 3 n + 4！

int sum(int array[], int n) {
    int result = 0;
    for (int i = 0; i < n; ++i) {
        result += array[i];
    }
    return result;
}

再貼一次程式讓大家回顧一下，你會發現這完全是有跡可循的，因為你稍微看一下會發現其實步驟數等於

1 (宣告 result = 0) + 
1 (宣告 i = 0) +
1 (執行 i < n) * n +
1 (執行 result += array[i]) * n +
1 (執行 ++i) * n +
1 (當i == n時，執行讓迴圈跳出的那一次 i < n) +
1 (執行 return result)
= 1 + 1 + 1*n + 1*n + 1*n + 1 + 1
= 3n + 4

結果 f(n)=3n+4，這就是該程式片段、或稱陣列加總演算法的步驟數統計。你...覺得這樣的分析方法如何呢?

老實說我覺得超爛XD 首先！我必須得在每個步驟上進行計數，然後得推測結果與輸入之間的數學關係，現在是因為陣列加總是個簡單又單純的演算法，如果狀況稍微複雜一點整個分析會變得有夠困難！

而且真的有必要分析這麼仔細嗎？還記得我們將加減乘除記憶體存取等執行時間與輸入無關的「基本操作」列為步驟的理由之一是什麼?

二來因為程式中每個動作(存取、寫入記憶體、加減乘除等)若要細究它們的時間是一項大工程，而且這樣做很沒必要，因為老實說它們速度差異並沒有很大，因此「不管它們是黑貓、白貓，會捉老鼠就是貓」，把它們都歸類為「步驟」作為基本單位來分析是很棒的。

我們都已經無視了這些不同操作的微小差異，將它們一視同仁列為一個「步驟」了，那為什麼不乾脆讓我們的步驟"變大一點"，像下面這樣：

令 (宣告 result = 0) + (宣告 i = 0) + (當i == n時，執行讓迴圈跳出的那一次 i < n) + (執行 return result) 為步驟 a
令 (執行 i < n) + (執行 result += array[i]) + (執行 ++i) 為步驟 b
則 sum() 的步驟數變為：
f(n) = a + b * n
根據「步驟」的定義"執行時間必須與輸入無關"、"程式中在語法或語意上具有意義的單一片段"，可以發現 a 和 b 均符合，因此它們是單一步驟可被計為1：
f(n) = 1 + 1 * n = 1 + n
然後多出來的 1 老實說看起來有點多餘，但因為它與輸入無關、且為具有意義的單一片段，因此我們可以再把它和 n * 1 中的某個 1 合併，最後結果：
f(n) = n

這樣沒問題吧！我知道你可能會擔心（至少我自己當初學到這邊就很在意）：這樣不斷忽略掉一些微小的時間成本，到後來不會估計失準嗎？

其實這不需要過度擔心，因為一點點微小的成本其實對電腦來說根本微不足道，要知道光是你自家的電腦，一秒鐘一次算完 100,000,000 左右的四則運算問題根本easy peasy，且就算是像剛剛 3n 左右的步驟被估計成 n 這也不是什麼大問題，因為區區三倍左右的差距，我等台積電晶片製程做好一點讓 CPU 快一點、或拿多台一點電腦平行運算炸下去就可以輕輕鬆鬆彌補了，不論 n 再怎麼多都一樣，因為只要新 CPU 做 1 步耗時=舊 CPU 做 4 步耗時，這樣別說速度一樣，甚至還會比我們想像的更快一點點。

在做估計時最重要的是找出那些會造成致命差距的因素！那些無論台積電工人的肝再硬、平行再多台電腦都無法彌補的「致命差距」。

因此可以發現我們其實就連詳細的步驟數都不必知道，我們真正需要的是一個步驟數的「估計」，一個能找出「最痛點」、忽略一些沒那麼重要的因子的「估計」方法，而這正是我們下一段會提到的。