---
title: CP進階 02.complexity
tags: 1th,CP進階
---
# CP進階 02.complexity
[ppt](https://drive.google.com/file/d/1SamC0saDCvTkmf1jGYddbrSJM3BW1gUj/view?usp=sharing)
[題單](https://codeforces.com/contestInvitation/7db5bb8abb218500b29108323faa572fc2664abd)
[題解](https://drive.google.com/file/d/1yFdzUP8NrOWNn1yv5btiNUqPL9cJ_U_3/view?usp=sharing)
author: __Shioko

## 複雜度(complexity)

在寫程式的時候，我們時常要知道一個程式大概需要跑多久、消耗多少記憶體，
來去評估不同的演算法的效率，其中以直接實作並執行會是最準確的，
但是如果我們有很多個方案要比較，且想要使用跑得最快的那一個，
那直接把每個方案都實作出來就會顯得很多餘、浪費時間，
因此我們需要了解如何在程式寫出來之前估計他們的效能(時間/空間等)。

#### 估計方式

至於該如何估計呢？最直觀的方式就是先假設程式的每個指令都花費相同的時間(實際上當然不是，像取模就會比四則運算慢很多)，
再去計算一個程式跑的指令數對於某個變因的函數$f(n)$，
來估計一個程式的效率。

以計算$n$個元素總和的程式為例:

  int n;
  cin >> n;

  int sum = 0;
  for(int i = 0; i < n; i++) {
    int val;
    cin >> val;
    sum += val;
  }

  cout << sum << endl;

稍微數一下上面程式跑的指令數，
是$3$(for前面)$+ 1$(宣告for的i)$+ 5 \times n$(for迴圈裡面的指令數乘n)$+ 1$(多一次的check)$+ 1$(cout)
也就是$5 \times n + 6$個指令，
即對於變因$n$(輸入資料量)，這個程式的時間複雜度為
$$f(n) = 5n + 6$$

而另一個計算總和的程式怎麼樣呢？

  int n;
  cin >> n;
  vector<int> arr(n); \\建立一個n格的動態陣列
  for(int i = 0; i < n; i++) {
    cin >> arr[i];
  }
  int sum = 0;
  for(int i = 0; i < n; i++) {
    sum += arr[i];
  }
  cout << sum << '\n';

稍微數一下會是$2 + n$(建立n格大的陣列)$+ 1 + 3 \times n + 1 + 1 + 1 + 3 \times n + 1 + 1$
也就是$7 \times n + 8$個指令，
即對於變因$n$，這個程式的複雜度為
$$f(n) = 7n + 8$$

ps. 雖然開一個$n$格大的陣列是一行指令，可是應該把它視為做$n$次記憶體分配才是對的喔～

比較這兩者跑的指令數，可以知道前者在時間上明顯比較好，
但是每次都要細細的數有幾行指令要跑不會太麻煩嗎？
而且既然每一種指令跑的時間不太一樣，
且根據執行機器的不同、機況、環境等，同一份程式跑的時間也會不太一樣，
那麼精細的去計算有幾行指令好像也沒什麼意義，
我們只要知道一個程式”大概“會跑多久似乎就足夠了，
因此我們常常用漸進符號之一「大O表示法」(big-O notation)來表示一個程式的時間複雜度。

#### 大O符號(Big-O notation)

所謂的大O符號，為漸進符號的其中一種，是用來描述一個函數$f(n)$在$n$趨近於極限時，函數的成長趨勢。

雖然本身是描述數學上函數的一個符號，但也可以在演算法分析的時候來大略描述一個時間複雜度的函數。

大家在社課的時候應該聽過「把最大量級以外的東西去掉、常數去掉」就是big-O notation的表示，不過這只是一個簡略的說明，
這裡會給出一個更為嚴謹的定義，以更正確地使用這個符號。

$O(g(n))$代表以下函數的集合：
$O(g(n))$ $=$ {$f(n): 存在常數c, k使得對於所有n \ge k都滿足0 \le f(n) \le cg(n)$}

白話來說就是如果一個函數$f(n)$是$O(g(n))$($g(n)$是$n^2$等等的...)
那變因$n$在超過某個常數$k$之後，一定可以找到一個$g(n)$的常數倍$cg(n)$使$cg(n)$永遠大於$f(n)$，畫成圖大概像這樣。

舉個例子，假設有一個程式跑的指令數是$f(n) = 3n^2 + 4n + 5$，
那我們可以說他的時間複雜度是$O(n^2)$。
因為我們可以找到一個$cn^2$在$n$足夠大的時候大於$f(n)$。
ex. 取$c = 4$，則$0 \le f(n) \le 4n^2, n \ge k = 5$

如果再仔細觀察一下，會發現對於一個函數的big-O notation並不需要取到最剛好的那個量級，
像是上面那個$f(n)$，你可以說他是$O(n^2)$，也可以說他是$O(n^3), O(n^{100}), O(n!)...$，不過通常會取最緊的上界。

當我們找到一個$O(g(n))$能夠"卡住"原本的複雜度函數$f(n)$，
那我們就可以直接用$g(n)$來估算程式跑的指令數，且實際跑的數量一定會小於$g(n)$的常數倍。

透過big-O notation，我們可以快速、大略地估計程式的執行效能，
藉此來比較不同演算法的效率，像是比較一下最上面那兩個例子的時間複雜度，
可以發現都是$O(n)$，因此我們可以說他們大略上的效能是差不多的。
(一個量級的比較圖)

#### 用複雜度估計執行時間

我們知道了一個程式的複雜度之後，還要知道如何轉換成執行的時間，
慣例上一般的judge在$1$秒內大概可以跑$10^8$個指令(CodeForce可以到$10^9$)，
依照這個去推就可以了。

ex. $n \le 1000$可以在一秒內跑完$O(n^2)$的演算法，
因為$1000^2 \le 10^8$。

#### 常數(constant factor)

「等等，剛剛那兩個程式明顯就是前者比較快啊，憑什麼說他們兩個的效能差不多？」
沒錯，這就是一個Big-O notation的問題，一個$O(n)$時間複雜度的程式，
實際上是$n, 10n$還是$10000n$，沒有人會知道，
因此當兩個演算法的複雜度相同的時候，硬要比較他們的優劣的話，
就得估計他們項次前面的那個數字$1, 10, 10000...$，也就是常數(constant factor)。

而很遺憾地，我們無法在實作之前確切地知道那個常數，
通常只能依靠經驗判斷(像是遞迴的常數會比較大之類的)，
但是也不用太擔心，大部分的題目會給你一個足夠寬鬆的限制，讓你不會因為常數而失敗。

#### 時間複雜度越小就越好嗎?

讀完上面的敘述之後，可能很多人會覺得「量級小的時間複雜度一定比較好」，
其實也不全然，要記得上面的東西都是建立在「$n$足夠大」的前提下，
因此在$n$很小的狀況下，像是$O(n^2)$可能和$O(n)$實際跑的時間是差不多的，
這時候就可以從其他面向(實作難度、消耗空間、自己的熟練程度)等等來做評估。

ex.
$n = 10$時，$n^2 = 100, n = 10$，兩個的執行時間只差了十倍。
$n = 1000$時，$n^2 = 10^6, n = 10^3$，執行時間差了一千倍。

#### 空間複雜度(space complexity)

還有一點，大O符號不是只能用在估計時間上面喔～
估計消耗的記憶體也是常見的用途之一，
以上面例子為例，前者並沒有額外分配空間，因此空間複雜度是$O(1)$，
後者分配了一個$n$格的陣列，空間複雜度是$O(n)$。

#### 其他漸進符號

除了big-O notation(上界)以外，其實還有little-o(嚴格上界)、big-omega(下界)、
little-omega(嚴格下界)、big-theta(嚴格上下界)等等的符號，
不過在CP不太會用到就是了xd。

## 思考

1. $O(2^n)$和$O(3^n)$是同樣量級嗎？
2. 請從小到大排序$O(lgn), O(1), O(n^2), O(lglgn), O(nlgn)$