Time Complexity (時間複雜度)

照理來說，如果時間與記憶體無限，那麼世界許多難題都能輕鬆解決

• 圓周率 Pi 小數點後 一兆兆位是什麼

• 猜銀行帳號密碼

• 玩手機遊戲( 傳說對決 )角色走的路徑，是不是最短？

Question: 從紅點走到綠點為什麼不是最短路徑

以下程式碼會執行多久？

#include <bits/stdc++.h>
using namespace std;

int main(){

    long long i, a=0, b=1;

    for( i=0 ; i<100000000 ; i++ ){
        a = a+b;
    }

    return 0;
}

Ans: 因不同電腦而異， 0.01 ~ 10秒都有可能， 一般來說，檢定時的電腦大約 0.1 ~ 1 秒左右

換句話說，跑 一億 次運算大約一秒鐘

Big-O

在最差的狀況下，演算法執行時間需要多久

我們表示方法是 O(x), x 可以想像是最多要幾次運算，我們通常會忽略常數

Ex. O( N ) = O( 2*N ) = O ( 9*N ) = O( N/2 )

Ｏ（1）

long long a = 3, b, c;

b = a;

long long a = 3, b, c;

b = a * 2;

Ｏ（N）

const int N = 5;
int arr[ 5 ] = {1,3,4,5,6};

for ( int i = 0 ; i < N ; i++ )
    cout << arr[i] << " ";

const int N = 5;
int arr[ 5 ] = {1,3,4,5,6};

for ( int i = 0 ; i < N-1 ; i++ )
    arr[i] = (arr[i] + arr[i+1]) / 2;

Ｏ（N ^ 2）

const int N = 5;
int a[ 5 ] = {1,3,4,5,6};

for ( int i = 0 ; i < N ; i++ )
    for ( int j = i+1 ; j < N ; j++ )
       if ( arr[i] < arr[j] )
          swap( arr[i], arr[j] );

Ｏ（N * logN）

const int N = 128;
for ( int i = 1 ; i <= N ; i++ )
    for ( int j = 1 ; j <= N ; j *= 2  )
        ...

時間複雜度為 O(log n) 的演算法（這邊的 log 都是以二為底），代表當輸入的數量是 n 時，執行的步驟數會是 log n。（讓忘記 log 是什麼的同學們複習一下，當 log n = x 的意思是 n = 2^x，如果這部分的腦細胞尚未復活，且讓我們先記住 n = 2^x，再來看看例子。）

舉例來說，當 n = 4，程式會在 2 個步驟完成（4 = 2²）；n = 16 時，程式會在 4 個步驟完成（16 = 2⁴），以此類推。

組合型

下面的程式碼複雜度是多少，大概要跑幾秒呢？

for( i=0 ; i<N ; i++ )
    for( j=0 ; j<N/2 ; j++ )
        ...
for( i=1 ; i<N ; i*=2 )
    for( j=0 ; j<N ; j++ )
        ...

Ans: O( N^2 ) + O( N*logN ) = O( N^2 )

討論

當有 100000 個數字要排序，用 Insertion Sort 的複雜度是多少？ 大概需要多少時間

補充資料

從時間複雜度認識常見演算法