何謂演算法 what is algorithm

• a finite sequence for solving mathematical problem or performing a computation
• step by step procedure to solve a problem
• 被定義完善的，可用電腦來執行用來解決問題的有限步驟或順序
• 簡單說就是用來 一步步解決問題的程序

two ways to get the value of sum

假設有兩個記算總和的 function

// method one
function getSum1(n){
    let sum = 0;
    for(let i =0;i<=n;i++){
        sum+=i;
    }
    return sum;
}

function getSum2(n){
    return (n*n+n)/2;
}

從1累加到10，兩個 function 都可以獲得相同的答案=55，
執行完 function 也都可以馬上得到答案，體感上似乎感受不出兩者的差異

但如果累加的值(input size)更大的話呢？
假設從1累加到1000，這兩個 function 分別需要多少時間？

新增 console.time & console.timeEnd 來看看執行所需的時間

console.time();
getSum1(1000);
console.timeEnd();

console.time();
getSum2(1000);
console.timeEnd();

這時候就可以明顯看出 getSum1 比起 getSum2 花費更多時間

所以 getSum2 較於 getSum1 效率則較高

How to compare algorithm?

基於資源的有限，可以從不同面向來進行演算法比較

• 時間複雜度 time complexity
  比較不同演算法分別花費多少時間，花費越少時間效率則越高

• 空間複雜度 space complexity
  記憶體是有限的資源，若該演算法會花費多少空間（main memory & disk space），花費越少空間效率則越高

• 準確度與正確性 accuracy and correctness
  當處理關於數字上與機率性的問題，準確度與正確性相當重要，偏差值越小與產出的結果正確率越高，則為更有效率的演算法

What is complexity

• When we refer to the complexity, we are often talking about time complexity 談到複雜度，多數指的是時間複雜度
• use f(n) to show the complexity equation complexity and input size
• the time complexity is depend on the input size and growth rate of the algorithm

簡而言之 growth rate + input size 與 time complexity 就是因果的關係

Growth rate

Algorithms can't grow by itself, but the time taken by it for solving the problems might grow.

As the input size increases, the time taken by the algorithm grows in accordance with its time complexity.

當 input 的值越來越大，則對應付出的代價（time & space）則會根據演算法本身的複雜度跟著增加，以下以圖片作說明，x軸/橫軸表示 n = input size，y軸/縱軸表示 cost(time or space)

當 input size 隨線性增長，growth rate 也會以線性增長(linear growth rate)
E.g: n=10 , x*10 , x is positive constant
當 input size 隨指數增長，growth rate 也會以指數增長(exponential growth rate)
E.g: 2 raised to n , n=2 cost=4 , n=6 cost=64
另外要注意的是，a,b>=1 , a的n次方成長速度大於n的b次方
E.g: n=2 a=6 b=6, 6*6=36 2^6=64
其中 n!(n階層) 即便 input size 還沒到相當大的數，其耗費的 cost 增長的速度相當驚人
E.g: n=3 cost=1*2*3=6 ,n=7 cost=5040

斜率越小的線表示，當 input size 大到一定程度的時候，cost 相對於其他斜率大的線較緩慢上升

Exercise of comparing growth rate

Q:For the growth function
2 raised to n, type a value (a positive integer) for which this function is the most efficient of the six:

• n!
• 2 raised to n(2的n次方)
• 2n raised to 2(2n的2次方)
• 5nlogn,
• 20n
• 10n

If there is no integer value for which it is most efficent, type "none".

Note: Assume all logs are base 2.

Ans: 4
將結果分別算出來
n!, cost=1*2*3*4=24
2 raised to n, cost=2*2*2*2=16
2n raised to 2, cost=(2*4)*(2*4)=64
5nlogn, cost=5*4*2=40
20n, cost=20*4=80
10n, cost=10*4=40
可知當n=4時，complexity of 2 raised to n 的值在這六種中會最小

相關資源

What methods can you use to compare algorithms for the same task?
https://www.linkedin.com/advice/1/what-methods-can-you-use-compare-algorithms-same-task
Comparing Algorithms
https://opendsa-server.cs.vt.edu/OpenDSA/Books/CS3/html/AnalIntro.html
Rate of growth of an algorithm
https://youtu.be/2PydAvq6zvQ?si=2cukdXdR31ybedzD
What is the difference between the growth rate of an algorithm and the running time of an algorithm?
https://www.quora.com/What-is-the-difference-between-the-growth-rate-of-an-algorithm-and-the-running-time-of-an-algorithm