演算法分析
怎麼定義演算法比較好 ? 1. 執行速度快(time) 2. 占用電腦記憶體空間少(space)
ex
// 1 + 2 + ...+ n
function fun1(n) {
let sum = 0
for (let i=1; i<=n; i++) {
sum += i
}
return sum
}
function fun2(n) {
return (1 + n) * n /2
}
console.log(fun1(10)) // 55
console.log(fun2(10)) // 55
在 index.html 引入 <script src="./test.js"></script>
test.js 檔案,在幫兩個演算法做計時
let time1 = window.performance.now()
fun1(100000)
let time2 = window.performance.now()
console.log('fun1 takes time', (time2 - time1)/1000)
let time3 = window.performance.now()
fun2(100000)
let time4 = window.performance.now()
console.log('fun2 takes time', (time4 - time3)/1000)
- 重新整理頁面,每次計時結果都不同
- 絕大多數情況, fun2 執行時間小於 fun1
- 小結:time and space are the concerns。可以利用計時知道花多久時間,但不實際。原因:(1)不穩定:同一台電腦不同次執行得到結果不同、(2) 不同電腦的硬體設備等級不同。
What's Complexity
- when analyzing the complexity of an algorithm, we calculate the (time or space) complexity.
如何計算時間複雜度 ?
- Generally, every addition, subtraction, multiplication, division comparison counts as one operation. (加減乘除與比較每一個都被算做一個 operation)
- Complexity means given an input size, how many operations do we need to perform in an algorithm ?(在寫的演算法裡,總共用到多少 operation。如果用到的 operation 越多,不論使用甚麼機器我所花費的時間就越多)
- We use function f(n) to show the equation of complexity and input sizes.f(n) 表示它的複雜度,其中 n 表示他的 input size,這表示複雜度與 input size 是呈一個函數的關係。
ex1:幾個 Hello
A:14 個
function example(n) {
// 迴圈從 0 跑到 5 執行 6 次,所以得到 6 個 Hello
for (let i = 0; i < 3*n; i++) {
console.log('Hello')
}
// nested for loop 外圈兩次,內圈兩次,所以總共有 4 個 Hello
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
console.log('Hello')
}
}
// 最後執行 4 次 Hello
console.log('Hello')
console.log('Hello')
console.log('Hello')
console.log('Hello')
}
example(2)
如果 example(n) 最後會印出幾個 Hellos ?
答:f(n) = n^2 + 3n + 4 (次)
- 第一個迴圈會執行 3n 次,每次都會引出一個 Hello,所以總共會印出 3n 個 Hellos
- 第二個巢狀迴圈會執行 n^2 次,每次都會引出一個 Hello,所以總共會印出 n^2 個 Hellos
- 最後還會再印出 4 次 Hellos
這個 f(n) = n^2 + 3n + 4 代表甚麼 ?
數學上 f(n) 與 n have quadratic relation. => 他們是呈平方關係,也就意味 n 成長一點點,f(n) 會爆炸性成長
function example(n) {
// 迴圈從 0 跑到 5 執行 6 次,所以得到 6 個 Hello
let counter = 0
for (let i = 0; i < 3*n; i++) {
counter ++
}
// nested for loop 外圈兩次,內圈兩次,所以總共有 4 個 Hello
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
counter++
}
}
// 最後執行 4 次 Hello
counter += 4
return counter
}
for (let i = 2; i < 10; i++) {
console.log(`example(${i}) will print out : ` + example(i) + ' Hellos')
}
Analysis of fun 1 and fun 2
要判斷複雜度低的第一件事,就是計算有多少 operation。
- fun1() 的 f(n) = 3n (因為 i <= n 、 i++ 、sum += i 也要算入,所以每執行一圈,就要執行 3 次 operation,又總共要執行 n 次 forloop,故 3 * n);數學關係為 linear
- fun1() 的 f(n) = 3 (因為);數學關係為 constant
- 當 n 很小時,兩者的差異不大,然而當 n 很大時,兩者的差異很大。
Big O Notation (超重要)
為甚麼很重要 ?
- 他是一個衡量演算法重要的工具,如果不知道他會不知道如何對演算法進行優化。
- 面試會被問到這個演算法 Big O 的值是甚麼
甚麼是 大 O
- Big O notation is a tool that describe the limiting behavior of a function when the argument (程式裡是指 input 的意思) towards a particular value or infinity. 當 input n 的值不斷擴大/逼近無窮,f(n) 的值會走去哪裡
- Big O notation has a worst case scenario, which means it shows the general trends of complexity when the size of inputs is extremely large. 大 O 表最壞的情況打算,當 input size 趨近無窮,他會展示演算法複雜度的成長趨勢
如何計算大 O
- constant doesn't matter => 將 constant 化成 1
- small terms don't matter
- logarithm base doesn't matter => 底數不重要
f(n) = 3n => O(n)
f(n) = 3n^2 + 4n + 4 => O(n^2)
f(n) = log 以 2 為底 指數為 n => O(logn)
f(n) = 5 => O(1) 因為將 5 化成 1
asympotic
1. Understanding Big O in math
- def:The function f(n) = O(g(n)) iff ∃ c, n0 st 0 <= f(n) <= c * g(n) ∀n >= n0 (c * g(n) 定義了 upper bound,所以 big O notataion defined 了一個函數他的 upper bound behavior 是甚麼)
- big O 的值原則上會以最小的 O 值表示,這樣才能反映他的特性。儘管我們知道 O(n) = O(n^2)
- ex:
2. Understanding Big Ω in math
- def:The function f(n) = Ω(g(n)) iff ∃ real number c, n0 st f(n) >= c * g(n) >= 0 ∀n >= n0 (c * g(n) 定義了 lower bound,所以 big Ω notataion defined 了一個函數他的 lower bound behavior 是甚麼)
- Big Ω 表示演算法最低限度的複雜度是甚麼,會介意 Big Ω 是因為演算法無論怎麼改進,總會有最低限度的臨界值,使的這個函數沒辦法變得更好
- Big Ω 的值原則上會以最大的 Ω 值表示,這樣才能反映他的特性。儘管我們知道 Ω(n) = Ω(log(n))
- ex1:insertion sort,O(n^2) and Ω(n),無論如何讓他變得更好,他最少時間複雜度就是 Ω(n)
- ex2:
3. Understanding Big Θ in math
- def:The function f(n) = Θ(g(n)) iff ∃ positive real number c1, c2, n0 st 0 <= c1 g(n) <= f(n) <= c2 g(n) ( Big Θ 定義 average boung )
- ex
小結
Big O in Arrays and Objects
- analysis of arrays and objects:處理資料方式包含 insertion / removal / searching / access
- js 原生 function 被寫成時就有自己的 Big O,我們要先認識他們的 Big O 才會避免之後學習演算法、資料結構發生一些常犯的錯誤
Object
- insertion : O(1) => 不管物件多麼龐大,幫他加入新的資料所需的時間都一樣
- removal : O(1)
- searching : O(n) => 要找尋物件裡面有沒有某個 property,他會從第一個 property 一路往下找到最後一個,如果沒有找到就會告知沒有,若有找到就會馬上通知並停止尋找
- accessing : O(1) => 因為 hash table (快速一次性地找到資料且占用記憶體也不大),所以 hugeObj.age 的時間與 tinyObj.age 相同
Array
- insertion : push O(1) / unshift O(n)
- push (加在 array 的最後面):因為只要在 array 最後面再加一格,所以是 O(1)
- unshift (加在 array 的最前面):unshift 後不僅 array 的總長度改變,新增加的那格的 index number 是 0,舊 array index number 是 0 的變成 1,對於陣列每個元素都要改變 index number,所以他的時間複雜度會是 O(n)
- removal : pop O(1) / shift O(n)
- searching : O(n) => 要找尋陣列裡面有沒有某個 element,他會從第一個 element 一路往下找到最後一個,如果沒有找到就會告知沒有,若有找到就會馬上通知並停止尋找
- accessing : O(1) => 因為 hash table (快速一次性地找到資料且占用記憶體也不大),所以 hugeArr[999] 的時間與 tinyArr[9] 相同
ex1
他的 big O 是多少 ?
let n = 5
let arr = [1, 3, 5, 7, 9]
for (let i=0 ; i<n; i++) {
arr.push(10)
}
console.log(arr) // [ 1, 3, 5, 7, 9, 10, 10, 10, 10, 10 ]
答 = O(n)
ex2
他的 big O 是多少 ?
let n = 5
let arr = [1, 3, 5, 7, 9]
for (let i=0 ; i<n; i++) { // addition opertion n times
arr.unshift(10) // O(n)
}
console.log(arr) // [10, 10, 10, 10, 10 1, 3, 5, 7, 9]
答 = O(n^2)
小結
js Array 與 Object 都使用 hash table 所以 accessing 資料所花的時間是一樣的,不論物件或陣列多麼龐大。