時間與空間複雜度

程式解題時的一些常用術語

short	full-name
AC	Accept	答案正確
WA	Wrong Answer	答案錯誤
TLE	Time Limit Exceed	超時
MLE	Memory Limit Exceed	記憶體超量
RE	Runtime Error	執行錯誤
CE	Compile Error	編譯錯誤

---

程式的執行時間分析

電腦每秒可以執行多少次，取決於CPU，
以i7-10代的電腦來說，其CPU平均執行速度為2.53GHz ~ 5GHz (GHz =

${10}^9$ proces. per second)
而我們通常評估程式的時候，都會以

${10}^8$~

${10}^9$ 來衡量，此數值意義是代表每秒可以執行幾次，
也就是你評估出當前題目的時間複雜度會超過這個數值時，就可能會TLE。

---

程式的記憶體分析

對於一個程式的記憶體用量，取決於當前程式所佔用的記憶體最大值，
而對於大部分的程式片段來說，其記憶體上限為 4GB (4 Giga-Bytes)。

在電腦算數中

$\text{1K}=2^{10}\approx {10}^3,\text{1M}=2^{20}\approx {10}^6,\text{1G}=2^{30}\approx {10}^9$

請務必牢記以上的紅色數字
以上這些知識在大三的演算法分析時會有更詳細的教學

---

Big-O 表示法

其記錄數值的方式，便是用一個字母「O」的函式形式做表達，
其表示法常會省略掉 係數、常數項、低次項 的部分，以下舉例：

ex.

$50n$

$\Rightarrow O(n)$
ex.

$7n^2+3n+1$

$\Rightarrow O(n^2)$
ex.

$10\cdot ({\log }_{2}n{)}^3+1000\cdot {\log }_{2}n$

$\Rightarrow O({\log }^{3}n)$
ex.

$\sqrt{n}+({\log }_{2}n{)}^3+{\log }_{2}n$

$\Rightarrow O(\sqrt{n})$

(請注意，log函式的省略底數格式，在電腦時間分析相關部分，其底數通常為2)

	$n=10$	$n=100$	$n={10}^4$	$n={10}^8$	$n={10}^{16}$
$n!$	3628800	9.33e+157
$2^n$	1024	1.267e+30	1.9e+3010	3e+3e+7	1e+3e+15
$n^2$	100	10000	1e+8	1e+16	1e+32
$n{\log }_{2}n$	33.219280	664.38561	132877.12	2.6575e+9	5.315e+17
$n$	10	100	10000	1e+8	1e+16
$\sqrt{n}$	3.1622776	10	100	1000	1e+8
${\log }_{2}n$	3.3219280	6.6438561	13.287712	26.575424	53.150849

(紅色部分是超過

${10}^8$ 的數值)

---

時間複雜度(Time Complexity)

一個程式，或是一個演算法的時間效率，通常會記做「時間複雜度(Time Complexity)」，
常以 Big-O 來表示，以下舉例：

int total = 0;

for(int x = 0 ; x<N ; x++)
    total += total + x;
    
// 單迴圈，計算二階差級數和
// Time Complexity : O(N)

int m[N][N];

for(int x = 0 ; x<N ; x++){
    for(int y = 0 ; y<N ; y++)
        cout << m[x][y] << ' ';
    cout << '\n';
}

// 雙迴圈，印出 N×N 的陣列
// Time Complexity : O(N^2)

for(int x = 0 ; x<N ; x++){
    for(int y = 0 ; y<N ; y++);
    for(int z = 0 ; z<M ; z++);
}

// 複合雙迴圈，
// Time Complexity : O(N(N+M))

void run(int n){
    if(n)
        run(n-1);
}

// 遞迴
// Time Complexity : O(N)

void run(int n){
    if(n)
        run(n>>1);    // n>>1 == n/2
}

// 二分遞迴
// Space Complexity : O(logN)

---

空間複雜度(Space Complexity)

一個程式，或是一個演算法的(記憶體)空間用量，通常會記做「空間複雜度(Space Complexity)」，
也可使用 Big-O 來表示，以下舉例：

int arr[N][M];

// 二維陣列
// Space Complexity : O(NM) = NM bytes 

int SumOfRange(int L, int R){
    if(L>R)
        return 0;
    
    return L + SumOfRange(L+1,R);
}

// 遞迴形式的區間和 (N = R-L)
// Time Complexity  : O(N)
// Space Complexity : O(N)
// Max-Memory Usage : 8N bytes

int binary_search(int*arr, int L, int R, int tar){
    if(L>=R)
        return arr[L] == tar ? L : -1;
    
    int mid = (L+R)/2;
    if(tar > arr[mid])
        return binary_search(arr,mid+1,R,tar);
    else
        return binary_search(arr,L,mid-1,tar);
}

// 遞迴版的二分搜尋法，N為陣列arr的長度 = R - L
// Time Complexity  : O(logN)
// Space Complexity : O(logN)
// Max-Memory Usage : 20logN bytes

int arr[100];
int L = 0, R = 100, tar, mid;

while(L<R){    
    mid = (L+R)/2;
    if(tar > arr[mid])
        L = mid+1;
    else
        R = mid-1;
}

// 迴圈版的二分搜尋法，N為陣列arr的長度
// Time Complexity  : O(logN)
// Space Complexity : O(1)
// Max-Memory Usage : 416 bytes

請注意，一段程式區段(scope{})執行完後，裡面所宣告的所以變數都會被釋放(包含指標變數)，
但被 new 的物件並不會被釋放，這些被 new 的物件必須要被 delete 後才會被釋放。

而記錄一個程式的空間複雜度，我們會用整個程式最大會一次占用多少記憶體來記錄。

通常紀錄程式的空間複雜度，不太會用Big-O表示，因為其很容易計算也很容易過量使用。

<友善提醒>
請務必注重 O(logN)算法 的潛力，其執行時間遠快於其他任何的執行時間。
也因此，有一句話是這樣說的：「高階的程式設計應當避免使用迴圈」