Aloha！又是我少女人妻Uerica！話說這次有很多以前的朋友同學們一起參加鐵人賽，，不但可以一起加油打氣，因為每天都會去收看大家的文章，真是收穫滿滿～啊。

常見的時間複雜度

延續昨日的嫩煎雞翅，大致說明了一下時間複雜度評估與判斷的方式和概念。但通常哪種程式碼的演算法是比較有效率的呢？先來看一下這張圖！x軸為執行時間、y軸為輸入資料量

圖片引用自 : http://bigocheatsheet.com/

圖示可見除非確定輸入資料量 (n) 很小，不然一般不建議使用指數階或階乘時間複雜度的演算法 (圖示的紅色區塊)。

實際範例

以下範例均將 n 訂為 10, x 值表示執行幾次。

常數階 O(1)
將 a, b 的值交換，無論 a, b 值中的數字多大都不影響步驟數。

let a = 10;
let b = 20;
let temp = a;
a = b;
b = temp;  

對數階 O(log n)
在下列 while 迴圈中的例子，i 每次進入迴圈都會乘 2 ，直到 i 值大於 n 為止，表示 2 的 x 次方大於 n 迴圈才會停止，而 x 值代表執行了幾次，n 值越大會讓步驟越多、執行時間越長。在 Big O 表示法的 log n 的底數因是常數，影響不大所以可省略。

2 ^ x = n
x = log2 n
= O( log n )

let i = 1;
let n = 10;
let x = 0;
while ( i < n ) {
    i = i * 2;
    x++ // 執行 1 次加 1
}
console.log (x); // 4

線性階 O(n)
下面例子中，程式執行的時間會隨著迴圈內的 n 做增加，其餘部分則不會受太多影響。

let n = 10;
let x = 0
for ( let i = 1 ; i <= n ; i++ ){
    x++;
};
console.log (x); // 10

線性對數階 O(n * log n)
O(n * log n)與前面說的對數階 O(log n) 相似，在外包一層for迴圈，使 n 個循環次數乘上 log n

let n = 10;
let x = 0;
for (let i = 1 ; i <= n ; i++){
    let j = 1;
    while (j < n) {
        j = j * 2;
        x++;
    }
}
console.log (x); // 40

平方階 O(n^2)
以前做題目最愛用的雙迴圈，竟然是紅色警戒區（嚇到吃手手），顧名思義就是迴圈內再跑一個迴圈，資料量若會成長則不建議使用！

let x = 0;
let n = 10;
for (let i = 1 ; i <= n ; i++){
    for (let i = 1 ; i <= n ; i++){
        x++;
    };
};
console.log (x); // 100

參考資料：

[資料結構] 演算法評估與資料型別

時間複雜度和空間複雜度，大 O 表示法【數據結構和算法入門2】

好的～今天就先到這邊啦！明天再談空間複雜度吧！晚安掰掰！