【在厨房想30天的演算法】Day 03 那个时间复杂度会让人生变复杂吗？

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】

好的～今天就先到这边啦！明天再谈空间复杂度吧！晚安掰掰！