何謂複雜度

通常在解題或打競程時都會看到題目有時間與記憶體限制，而這基本上會跟你程式的時間/空間複雜度（Time／Space Complexity）有關。

ex：以 Codeforces 為例，上面會設定每個測試案例的時間限制和記憶體限制。

這些限制通常用來表示你程式的執行效能，因此在解題時，我們通常需要確保程式在時限內完成執行，避免遭遇到 TLE（Time Limit Exceed，超過時間限制）或 MLE（Memory Limit Exceed，超過記憶體限制）的問題。

時間／空間複雜度（Time／Space Complexity）

電腦的計算速度是固定的，且執行時間與計算量成正比，因此時間複雜度通常用來表示計算量，而不是實際的執行時間。

空間複雜度則是指程式執行過程中所需的最大記憶體空間。

在程式競賽中，我們通常會優化空間以換取執行速度，因此空間複雜度不常被考慮，但時間複雜度對於競賽程式非常重要。

如何表示和估算時間複雜度

時間複雜度通常用大O符號表示，正式名稱為 Big O，但通常我們只稱之為「歐」。

我們估算時間複雜度時，通常會將每行程式碼視為一個時間單位，因此計算時間複雜度時會考慮變數的計算量和程式碼的執行行數。因此，我們常見的時間複雜度包括 等。

通常在競賽程式中，我們會忽略常數，因為它們影響計算量的方式很多，例如加法、減法、乘法和除法，因此我們通常會忽略常數，只關注最壞情況下的計算量，這代表複雜度。不過，不要忽視常數，因為在某些情況下， 的增長速度（斜率）可能差很大，因此常數在一些情況下也很重要，但通常只有在無法進一步優化複雜度時才會考慮，這種情況稱為「壓常」。大多數情況下，常數不像指數那麼影響成長速度。

常見時間複雜度

1. ：陣列讀取
   可以看到他只做了輸入字元陣列並輸出，因此複雜度為

#include <iostream>
using namespace std;
int main(){	
	char ch[100];
	cin >> ch;
	cout << "hello, " << ch << "\n";
	return 0;
}

2. ：線性搜尋（linear search）

int linearsearch(int a[],int n,int k){
    for(int i = 0;i < n;i++){
        if(a[i] == k){
            return i;
        }
    }
    return -1;
}

3. ：二分搜尋（binary search）

int binary_search(int l,int r,int k){
    while (l <= r){
        int m = (l + r) / 2;
        if (ary[m] == k){
            return m;
        }else if (ary[m] < k){
            l = m + 1;
        }else{
            r = m - 1;
        }
    }
    return -1;
}

4. ：合併排序（merge sort）

每次遞迴呼叫的函式複雜度是 ，而每個子問題在每次函式呼叫時都會縮小一半，因此這個情況和二分搜尋是一樣的，所以時間複雜度是。

void msort(int p, int q){
    int mid;
    if(p == q){
        return;
    }
    mid = (p + q) / 2;
    msort(p,mid);
    msort(mid + 1,q);
    merge(p,q);
}
void merge(int p, int q){
    // ...（合併排序的實作）
}

5. ：氣泡排序(bubble sort)

void bubblesort(int arr[]){
    int n = arr.size();
    for (int i = 0; i < n - 1;i++){
        for (int j = 0;j + 1 < n - i;j++){
            if (arr[j] > arr[j + 1]){
                swap(arr[j],arr[j + 1]);
            }
        }
    }
}

複雜度計算

綜合上面的例子和說明，估算複雜度的要點如下：

• 計算出程式最差情況下的計算量
• 忽略所有常數，包括常數項與常數係數
• 忽略不影響函數成長速度的部份，通常是所有非最高次項
• 用大 O 符號將計算量包裝起來，這樣就表示時間複雜度。