Day3: Big O — 时间复杂度与空间复杂度

每一种题目可能有数种的解法，那我们应该怎麽评估每种解法的优劣呢?以前的我应该会回答，当然是越简短的写法越好呀! 不过，写过leetcode之後，会发现有时候很简短的解法，执行效率反而看不见别人的车尾灯(吊车尾)，那麽leetcode是怎麽评断解法的好坏呢? 答案是透过时间复杂度和空间复杂度来评估。

• 时间复杂度(Time Complexity):执行函式需要花费的时间
• 空间复杂度(Space Complexity):执行函式会占用的记忆体空间

关於时间复杂度

• 演算法运算次数的增长效率
• 演算法的执行时间不是以秒计算的， 是以运算次数计算的
• 演算法的执行时间 ，不一定会随着元素数量的增加而等比增加

这边要特别注意，执行的时间并非以秒为单位，因为家用电脑与超级电脑的运算速度根本天差地远，比较秒数的话其实没有多大的意义，因此是用次数来作计算，而我们习惯用O来表示演算法的执行效率，作为评估演算法执行效率好不好的指标，当函式输入的Input 长度变长的时候，就可以了解演算法的效率趋势，效能差的演算法的曲线就会陡峭上升像是O(n²)而好的演算法的曲线会趋於平缓O(log n)。

*图片来源:*https://smootok.com/big-o-notation/

O(1) - 常数

不管输入的n为多少，都只要执行一次

//无论arr的length有多长，都只要执行一次即可
//ex : 找出index=2的值为何?
const arr = ['andy', 'peggy', 'debby'] 
console.log(arr[2])

O(log n) - 对数(n 是 2 的几次方)

输入8的话，log 8 = 3，也就是8 = 2³ (8是n的3次方)，所以经过3个步骤就可以找到我们要的答案，简单来说就是不断的剖半，像是二分搜寻法

O(n) - 线性

跑一次回圈，所以如果输入的n越长，执行的次数也会等比增加

//找出这个阵列有没有debby这个人,不用indexOf和includes话，就是土法炼钢，从头找到尾，一个一个慢慢找
const arr = ['andy', 'peggy', 'debby']
for(let i=0;i<arr.length;i++){
    if(arr[i]==='debby') return true;
}

O(nlog n) - 线性对数

ex:快速排序法，在之後的文章会有更详细的解说

O(n²) - 平方，n的平方

ex:用双回圈印出一个九九乘法表

//n*n=n²
for(let i=1; i<=9; i++){
   for(let j=i; j<=9; j++){
      console.log(`${i}*${j} = ${i*j}`)
   }
}

O(n!) - 阶乘

ex:n阶乘，ex: n x n-1 x … x 3 x 2 x 1

最理想的时间复杂度就是O(log n)或是O(1)

关於空间复杂度

执行程序占用的记忆体空间 ，占用越多越吃资源，一样也是用Big O来表示，而时间复杂度和空间复杂度两者是可以互相trade off的。

甚麽是trade off?

有时候可以用空间来换取时间 ，或是用时间换取空间，依照当时的使用情境来做取舍。

O(1)
不管输入的n为多少，都只会建立一个变数total，因此空间复杂度为O(n)

const add = (n) =>{
    let total = 0
    for(let i=0;i<n;i++){
       total += i
    }
    return total
}

O(n)
arr的长度会根据使用者输入的n来增长，因此空间复杂度为O(n)

const createArray = (n) =>{
    const arr = []
    for(let i=0;i<n;i++){
        arr.push(i);
    }
    return arr
}