閱讀前，建議可以參考Day1：閱讀指南＆為何選擇這個題目？

▌挑戰簡介

• 題目：計算機概論Ｘ30天

• 挑戰內容：連續30天紀錄計算機概論、離散數學、演算法、資料結構等課程，還有自己學習程式的心得體悟。

• 適合閱讀者：稍微會一點程式（最好是JS），知道什麼是迴圈、變數的入門，然後想知道如何分析程式的時間複雜度

• 不適合閱讀者：連程式都沒寫過、不知道什麼是迴圈、變數的超級超級外行＆寫程式多年，對演算法、數據結構、計算機解透徹的高手。（因為這是我初學的心得，因此內容會可能過於簡單且不夠嚴謹。）

▌要如何判斷一個程式是否有效率？

要判斷一個程式是否有效率，首先要定義何謂「有效率」。
一個有效率的程式有主要兩個特色：

• 程式運行時間少
• 程式佔據的內存少

本篇討論運行時間這件事好了，要怎麼知道運行時間？很簡單啊——把程式跑一遍，然後就知道時間了

太聰明了！沒錯。
以為我要阻止你嗎？沒有。

想知道a和b兩個程式哪個快，當然就是跑一遍囉！
很多程式上線之前也會做測試，因此直接測試當然是個方式。

But，但是，但是
實際測試會有一些限制，那就是很依賴測試環境還有數據狀況

同一個程式：

• 用不同處理器消耗的時間可能不ㄧ樣（用a處理器可能耗費0.01秒，b處理器可能0.02)
• 用不同電腦跑出的時間不ㄧ樣（用a電腦可能耗費0.01秒，b電腦可能0.02)
• 用不同數量的數據耗費的時間不ㄧ樣（輸入1000000個Data，跟輸入1個Data耗費的時間不一樣）
• 用不同狀況的數據耗費的時間不ㄧ樣（比如說如果想把數列從小排到大，那處理1,2,3,4跟4,3,2,1兩筆資料所耗費的時間不ㄧ樣，前者一定比較快，因為根本不用做什麼就已經是小排到大了）

因此，除了實際運行外，我們似乎還是需要一個不受環境、數據狀況能夠客觀描述程式的大概會耗費多少時間資源的方式這時候就需要——時間複雜度(time complexity)分析

▌時間複雜度(time complexity)分析

時間複雜度(time complexity)分析是什麼？它是一種不依賴直接運行程式，只要用肉眼觀察程式碼、掐掐拇指，然後大致可以計算出程式會耗費的時間資源的分析方式。

要怎麼做呢？看以下範例

▌計算程式時間

假設電腦每運行一行程式會耗費1個單位時間t

時間單位t的由各別電腦效能決定，可能是0.0000001或是0.000000001（看不同電腦）

我們來算算運行以下這些程式大概會花多少時間。。（以下用Javascript做範例）

function f1() {
    var a = 0   //耗費一個時間單位t
    console.log(a) //耗費一個時間單位t
}

這個function f1函式消耗的t+t=2t，也就是2個時間單位

function f2() {
    var a = 0 //耗費一個時間單位(t)
    for (var i = 0; i < 10; i++) {
        a++;  //耗費10個時間單位(t)，因為重複了10次
    }
    console.log(a); //耗費一個時間單位t
}

這個function f2函式消耗了10t+2t=12t，共12個時間單位

function f3(n) {
    var a = 0  //耗費一個時間單位(t)
    for (var i = 0; i < n; i++) {
        a++;  //耗費n個時間單位(t)，n是什麼由這個函式吃到什麼數據決定
    }
    console.log(a); //耗費一個時間單位(t)
}

這個function f3函式共耗費nt+2t=(n+2)t，共(n+2)個時間單位

function f4(n) {
    var a = 0; //耗費一個時間單位(t)
    for (let i = 0; i < n; i++) { //耗費n個時間單位(t)
        for (let i = 0; i < n; i++) { //耗費n個時間單位(t)
            a++;
        }
    }
    console.log(a); //耗費一個時間單位(t)
}

這個function f4函式共耗費(nｘn)+2=(n^2+2)t，也就是共n^2+2個時間單位

▌BigO表示法

整理一下

function f1：消耗了2t(時間單位)
function f2：消耗了12t(時間單位)
function f3：消耗了(n+2)t(時間單位)
function f4：消耗了(n^2+2)t(時間單位)

運行速度是f1>f2，至於f3、f4速度則要看n的大小決定

OK，那要怎麼客觀形容程式耗費的時間資源呢？傳統上會轉換成一個BigO函示來表示程式的時間複雜度

代換之後，變成如下

function f1：消耗了2t(時間單位) => 時間複雜度是O(1)
function f2：消耗了12t(時間單位) => 時間複雜度是O(1)
function f3：消耗了(n+2)t(時間單位) => 時間複雜度是O(n)
function f4：消耗了(n^2+2)t(時間單位) => 時間複雜度是O(n^2)

▌觀念澄清

可能會覺得很怪，為何f1、f2的時間複雜度相同?為何f3時間複雜度是O(n)?為何f4時間複雜度O(n^2)?

這邊要澄清一個觀念

O(n)不代表表執行時間，它代表的是執行時間隨著數據規模增長的變化趨勢
因此Big O又稱為漸進時間複雜度

為什麼f1、f2的時間複雜度相同？

function f1：消耗了2t(時間單位) => 時間複雜度是O(1)
function f2：消耗了12t(時間單位) => 時間複雜度是O(1)

由於O(n)代表的是執行時間隨著數據規模增長的變化趨勢，但對於f1、f2來說，這個程式根本沒有數據規模增長的問題。因此對電腦來說不管是2t還是12t，都是同個量級的程式，因此時間複雜度是O(1)

為什麼f3的複雜度是O(n)？

function f3：消耗了(n+2)t(時間單位) => 時間複雜度是O(n)

f3這個函式有數據規模增長的問題，當輸入的n愈大時，它消耗的時間愈多
那為什麼不是O(n+2)？
因為當n很大時（比如10萬），那個2可以被忽略計算，因此會省略2直接寫成O(n)

為什麼f4的複雜度是O(n^n)？

function f4：消耗了(n^2+2)t(時間單位) => 時間複雜度是O(n^2)

為什麼時間複雜度不是O(n^2+2)？

理由跟上面ㄧ樣，當n很大（比如10萬），那個2基本就是個零頭，因此會省略直接寫成O(n^2+)

▌一些實用技巧

從上面可以知道，函式消耗的時間單位不管是

• n(時間單位)
• n+1(時間單位)
• n+1000(時間單位)
• n+100000(時間單位)

它們的時間複雜度也可以寫成O(n)

可是，100000很大耶！n+100000個時間單位跟耗費n個時間單位明明就差很多！
沒錯！所以再次澄清一遍，O(n)不代表執行時間，它代表的是執行時間隨著數據規模增長的變化趨勢

在n很小的時候或許n+1跟n+100000執行時間或許有差，但是在n很大很大很大的時候n+1跟n+100000的運行時間是差不多的。

由於Big O觀察的是隨著數據規模增長消耗時間的變化趨勢
我們得到一個結論「只要關注那些影響時間變化最多的程式即可」

因此有一些技巧

▌技巧1.只要關注重複次數最多的部分（像是迴圈）

function f6(n) {
    var a = 0;  //可以直接省略
    for (let i = 0; i < n; i++) {
        a++;  //這個重複最多次，關注他就好了
    }
    console.log(a); //可以直接省略
    console.log("妳好"); //可以直接省略
    console.log("安安"); //可以直接省略
    console.log("給虧嗎") //可以直接省略
}

這個function f6函式雖然耗費n+5個單位時間，但是複雜度依然是寫作O(n)

▌技巧2.捨棄小量級的部分

那如果遇到下面的狀況呢

function f7(n) {
//a區塊
    var a = 0;
    for (let i = 0; i < n; i++) {
        a++;
    }
    console.log(a);
//b區塊
    var b = 0;
    for (let i = 0; i < n; i++) {
        for (let i = 0; i < n; i++) {
            b++;
        }
    }
    console.log(b);
}

在這個函式中，a區塊的複雜度是O(n)，b區塊是O(n^2)，這時候要怎麼辦？
答案是——直接省略a區塊的O(n)，該function f7函數的複雜度是O(n^2)

原因是什麼？

跟之前的邏輯一樣，當n很大的時候，n^2會遠遠大於n，使得n可以被忽略不計。

▌總結

• 要怎麼知道程式是否有效率？
  • 直接跑程式，看它跑的快不快。優點是方便，其實測試沒有不行，測試是好事，但就是必須接受測試結果會很依賴環境的缺陷。
  • 觀察程式碼，計算它的時間複雜度。優點是客觀，缺點是太廢算不出來。
• 時間複雜度是什麼？
  • 時間複雜度不等於「運行時間」，而是指「時間隨著數據規模增加的的變化趨勢」。在n很小的時候，O(n^2)跟O(n)消耗的時間可能差不多，但隨著n變大O(n^2)就會明顯地比O(n)慢。
• 時間複雜度怎麼看？
  • 只要關注執行最多的代碼就好，像是迴圈，迴圈中有迴圈，迴圈中有迴圈迴圈（無限loop）
  • 常數可以省略。例如城市中有O(n)的區塊，還有等於O(1)的區塊，那後者可以省略，最終整體的複雜度是O(n)
  • 小的量級可以省略。例如程式中有O(n^2)跟O(n)兩個區塊，那後者可以省略，最終整體的複雜度是O(n^2)

▌附上常見的時間複雜度

不逃脫以下幾種

• O(1)
• O(logn) //懶得示範呵呵
• O(n)
• O(nlogn) //例如歸併排序、快速排序就是這過
• O(n^2)
• O(n!)
• O(2n)

後兩者的複雜度很糟糕，因為當n愈大時，他們複雜度上升的速度非常快（意思是說運行效率就愈低），因此是糟糕的算法。他們稱為NP非多項是量級算法。

從上圖可以看不同算法，當Input數據愈大時，複雜度的增長趨勢

▌參考資料

・極客時間APP・《數據結構與算法之美》：前面兩個章節的學習心得

老師用Java寫，我改用JS寫並且順便省略一堆東西。因此如果對這個議題有興趣，可直接訂閱該專欄，不用看我這個菜鳥的心得（但你看完了哈哈）

＊終於進入了一些技術、理論的部分（呼）
＊每天寫那麼多字，頭真的有點暈，開始無法認真檢查了。有任何的錯誤歡迎指正QQ（鞠躬）