CP進階 02.complexity

ppt
題單
題解
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):\mathrm{存}\mathrm{在}\mathrm{常}\mathrm{數}c,k\mathrm{使}\mathrm{得}\mathrm{對}\mathrm{於}\mathrm{所}\mathrm{有}n\ge k\mathrm{都}\mathrm{滿}\mathrm{足}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)$。
因為我們可以找到一個

$c{n}^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)$