JavaScript, Math Review
Array Review
// array
let arr = ['Harry', 'Ron', 'Snap']// js for loop
for (let i = 0; i < arr.length; i++) {
console.log(i, arr[i])
}// forEach
arr.forEach((person, index) => {
console.log(person, index)
})
Object Review
// object
let Harry = {
name: 'Harry Potter',
age: 40,
married: true,
sayHi() {
console.log(`${this.name} says hi to you`)
}
}console.log(Harry.name)
console.log(Harry['name'])
Harry.sayHi()
Function Review
// function
function add(n1, n2) {
return n1 + n2
}let result = add(10, 15)
console.log(result)
Class Review
// class
// 做出相似的物件時使用let c1 = {
redius: 5,
getArea() {
return Math.PI * this.redius * this.redius
}
}let c2 = {
redius: 10,
getArea() {
return Math.PI * this.redius * this.redius
}
}console.log(c1.redius)
console.log(c1.getArea())
console.log(c2.redius)
console.log(c2.getArea())class Circle {
constructor(r) {
this.radius = r
}
getArea() {
return this.radius * this.radius * Math.PI
}
}let c3 = new Circle(5)
console.log(c3.radius)
console.log(c3.getArea())
Log Review
Log 定義
loga b = c 等於 a^c = b
log2 8 = 3 等於 2^3 = 8
log10 100 = 2 等於 10^2 = 100Log 運算規則
log a + log b = log ab
ex : log2 8 + log2 16 = log2 128
log2 8 = 3
log2 16 = 4
log2 128 = 7log a - log b = lob a/bloga n = n log a
ex : loga n = log(a*a*a*a) (乘以 n 個)
= loga + loga + loga (加上 n 個)
= n loga
Complexity and Big O Notation
The Idea of Algorithm
What is Algorithm ?
演算法是一個有限的、連續性且被定義好，可以被電腦執行的指令。
這些指令是用來解決問題、計算值。
演算法可以被視為一步一步解決問題的程序。Examples of Algorithm in real life
1. Google map 如何找到目的地的最短路徑 ?
2. YouTube 如何推薦影片給使用者 ?
3. excel 如何排序財報的順序、數值 ?
4. Facebook/Instagram 如何推薦可以加入的朋友 ?
Comparing Algorithms
It is important to compare algorithms?It two different algorithms can accomplish the same task, then why do we care about which one is better?Time and Space are the concerns.
如果花費較少的時間、較少的電腦記憶體空間，即為較好的演算法。// 1 + 2 + 3 + ... + n = sum
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
}let time1 = window.performance.now()
fun1(10000000)
let time2 = window.performance.now()
let timeDiff1 = (time2 - time1) / 1000
console.log(`It takes ${timeDiff1} secondes to run fun1`)let time3 = window.performance.now()
fun2(10000000)
let time4 = window.performance.now()
let timeDiff2 = (time4 - time3) / 1000
console.log(`It takes ${timeDiff2} secondes to run fun2`)
Complexity
What is Complexity?
1. 分析演算的複雜度的時候，會計算空間及時間複雜度。
2. 基本上，加減乘除、數值比較時都可以被算做一個 'operation'
3. 在演算法中，總共會用到多少的 'operation' ?
4. 通常會用 function f(n) 表示 Complexity 與 input sizes 之間的關係。function example(n) {
let counter = 0
for (let i = 0; i < 3 * n; i++) {
// console.log('Hello')
counter++
} for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
// console.log('Hello')
counter++
}
} // console.log('Hello')
// console.log('Hello')
// console.log('Hello')
// console.log('Hello')
counter += 4 return counter
}for (let i = 2; i < 10; i++) {
console.log(`example${i} will print out ${example(i)} Hellos `)
}
// 1 + 2 + 3 + ... + n = sum
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
}fun1
1. f(n) = 3n
(包含 let i = 1、i<= n、 i++)
2. Linear(線性關係) EX: y = 3xfun2
1. f(n) = 3
2. constant(常數關係)
Big O Notation
Big O Notation 是一個工具，用來描述 n 不斷擴大的時候，f(n)的走向。
Big O Notation 是一個最壞的情況的打算，展示一個演算法的趨勢。
Calculating Big O value
1. Constant doesn't matter. 常數不重要 f(n)=3n => O(n)
2. Small Terms don't matter. f(n)=3n^2+6n+4 => 0(n^2)
3. Logarithm Base (log 底數) doesn't matter. f(n)=log2^n => O(log n)Example 1
Q : f(n) = 2n what is the big O Of this algorithm ?
A : O(n)Example 2
Q : f(n) = 13n^3+6n+7 what is the big O Of this algorithm ?
A : O(n^3)Example 3
Q : f(n) = 4log2 n what is the big O Of this algorithm ?
A : O(log n)Example 4
Q : f(n) = 5 what is the big O Of this algorithm ?
A : O(1)
Common Big O of Algorithms
好
1. O(1)
2. O(logn)
3. O(n)
4. O(nlogn)
5. O(n^2)
6. O(n^3)
差
Understanding Big O
f(n) = 1500 => O(1)
f(n) = n => O(n)
f(n) = n + 1500 => O(n)
f(n) = n^2 => O(n^2)
Understand Big O Notation (Formal Definition)
Big O
ex : f(n) = 3n +6 , c = 7, g(n) = n, cg(n) = 7n
Big O in Arrays and Objects
Insertion, Removal, Searching, AccessObjects
Insertion => O(1)
Removal => O(1)
Searching => O(n)
Accessing => O(1)Array
Insertion => push O(1) unshift O(n)
Removal => pop O(1) shift O(n)
Searching => O(n)
Accessing => O(1)------------------------------let n = 5
let arr = [1, 3, 5, 7, 9]// O(n)
for (let i = 0; i < n; i++) {
arr.push(10)
}// O(n^2)
for (let i = 0; i < n; i++) {
arr.unshift(10)
}
Algorithm Design
Linear Search (Sequential Search)
此演算法會漸進的檢查 array 中的元素直到找到符合的元素，或遍歷完整個陣列。Pseudocode for Linear Search
Linear-search(array,n)
for i from 0 to array.length-1:
if(array[i] === n):
return i
return -1-------------------------------function linearSearch(arr, n) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === n) {
console.log(`Found number ${n} at index ${i}`)
return i
}
}
console.log(`Can not find ${n}`)
return -1;
}-------------------------------Overview of Linear Search
Worst Case Performance : O(n)
Best Case Performance : O(1)
Average Performance : O(n/2)
Binary Search
只能在 sorted array 中使用。
是一種更有效率的演算法。概念是每次挑選中間位置的資料來比對，若該資料小於目標值，則縮小範圍為左半部，反之亦然；因此使用這個方法每次比對後都可以濾掉一半的資料，以增快搜索速度。Pseudocode for Binary Search
BINARY-SEARCH(array, num)
min = 0
max = array.length-1
while min <= max:
middle = (min + max)/2
if num > arr[middle]:
min = middle + 1
else if num < arr[middle]:
max = middle - 1
else:
return middle
return -1-------------------------------function binarySearch(arr, n) {
let min = 0
let max = arr.length - 1
let step = 0 while (min <= max) {
step++
let middle = Math.floor((max + min) / 2)
if (n > arr[middle]) {
min = middle + 1
} else if (n < arr[middle]) {
max = middle - 1
} else if (n === arr[middle]) {
console.log(`Found ${n} at postion ${middle}.`)
console.log(`Found it after ${step} steps.`)
return middle
}
}
console.log(`Can not find number ${n}`)
return -1
}binarySearch(numbers, 20)
binarySearch(numbers, 298)-------------------------------8 > 4 > 2 > 1
log2 8 = 3
at most 3 steps to find what we want64 > 32 > 16 > 8 > 4 > 2 > 1
log2 64 = 6
at most 6 steps to find what we wantn > n/2 > n/4 > ... > 1
log2 n
at most log2 n steps to find what we want-------------------------------Overview of Linear Search
Worst Case Performance : f(n) = log2 n => O(log n)
Best Case Performance : O(1)
Average Performance : O(log )n
General Guide of Algorithm Design
寫演算法之前請先用人腦思考如何設計它。
不要讓電腦執行愚蠢的問題。Intersection Problem
EX : Intersection([15, 3, 6, 8, 24, 16], [11, 3, 9, 6, 15, 8])
// [3, 6, 8, 15]O(n^2)
function intersection(arr1, arr2) {
let result = []
for (let i = 0; i < arr1.length; i++) {
for (let j = 0; j < arr2.length; j++) {
console.log(arr1[i], arr2[j])
if (arr1[i] === arr2[j]) {
result.push(arr1[i])
}
}
}
console.log(result)
return result
}intersection([1, 2, 3], [5, 16, 10, 3, 1])
intersection([1, 2, 3, 7, 9, 19, 25], [19, 5, 16, 10, 3, 1])
Counter
為一種常見的技巧。
能夠有效地降低演算法的複雜度。function intersection(arr1, arr2) {
let result = []
let arr3 = arr1.concat(arr2)
let counter = {} for (let i = 0; i < arr3.length; i++) {
if (!counter[arr3[i]]) {
counter[arr3[i]] = 1;
} else {
counter[arr3[i]]++
}
}
console.log(counter) // loop over the counter
for (let property in counter) {
if (counter[property] >= 2) {
result.push(property)
}
}
console.log(result)
return result
}intersection([1, 2, 3, 7, 9, 19, 25], [19, 5, 16, 10, 3, 1])
Frequency Problem
Write a function that takes two strings and check if they have the same letters. Order doesn't matterfunction sameFrequency(str1, str2) {
// 將字串轉換為陣列
let arr1 = str1.split('')
let arr2 = str2.split('') if (arr1.length !== arr2.length) {
return false
} let counter1 = {}
let counter2 = {} for (let i = 0; i < arr1.length; i++) {
if (counter1[arr1[i]]) {
counter1[arr1[i]]++
} else {
counter1[arr1[i]] = 1
}
} for (let i = 0; i < arr2.length; i++) {
if (counter2[arr2[i]]) {
counter2[arr2[i]]++
} else {
counter2[arr2[i]] = 1
}
} for (let property in counter1) {
if (!counter2[property]) {
return false
}
if (counter1[property] !== counter2[property]) {
return false
}
}
return true
}console.log(sameFrequency('abbc', 'aabc'))
console.log(sameFrequency('aabb', 'abab'))
Average Pair
Write a function that given a sorted array of integers and a number.Find if there's any pair in the array that has average of the given number. Find all of them. There might be multiple pairs fit the condition// O(n2)
function averagePair(arr, avg) {
let result = []
for (let i = 0; i < arr.length - 1; i++) {
for (let j = i + 1; j < arr.length; j++) {
if ((arr[i] + arr[j]) / 2 === avg)
result.push([arr[i], arr[j]])
}
}
console.log(result)
}averagePair([-11, 0, 1, 2, 3, 9, 14, 17, 21], 1.5)
Pointer(箭頭)
是一個常見的技巧，用於演算法設計，Pointer並非正式的名字。
目的在於減少演算法的複雜度。Write a function that given a sorted array of integers and a number.Find if there's any pair in the array that has average of the given number. Find all of them. There might be multiple pairs fit the condition// O(n)
function averagePair(arr, avg) {
let left = 0
let right = arr.length - 1
let result = [] while (right > left) {
let temp_avg = (arr[right] + arr[left]) / 2
if (temp_avg > avg) {
right--
} else if (temp_avg < avg) {
left++
} else if (temp_avg == avg) {
result.push([arr[right], arr[left]])
right--
left++
}
}
console.log(result)
}averagePair([-11, 0, 1, 2, 3, 9, 14, 17, 21], 1.5)-----------------------------------------Sorted Array
(-11 + 21) / 2 = 5
5 > 1.5 如果要更接近平均，需要將 pointer 往左移一格
(-11 + 17) / 2 = 3
3 > 1.5 如果要更接近平均，需要將 pointer 往左移一格
(-11 + 14) / 2 = 1.5
1.5 === 1.5 找到的之後，pointer 都需要往內移一格
(0 + 9) / 2 = 4.5
4.5 > 1.5 如果要更接近平均，需要將 pointer 往左移一格
(0 + 3) / 2 = 1.5
1.5 === 1.5 找到的之後，pointer 都需要往內移一格
(1 + 2) / 2 = 1.5
Palindrome
Write a function that checks if the input string is a palindrome. Palindrome is a word that can be read forwards and backwards.EX:
'awesome' => false
'foobar' => false
'tacocat' => truefunction palindrome(str) {
let left = 0
let right = str.length - 1
while (left <= right) {
console.log(str[left], str[right])
if (str[left] === str[right]) {
left++
right--
} else {
console.log(false)
return false
}
}
console.log(true)
return true
}palindrome('tacocat')
palindrome('asdfsafeaw')
palindrome('amanaplanacanalpanama')
Subsequence Problem
A subsequence of a string is a new string that is formed from the original string by deleting some(can be none) of the characters without disturbing the relative positions of the remaining characters.
Write a function that checks if one string is a subsequence of the other stringfunction isSubsequence(str1, str2) {
if (str1.length === 0) {
console.log(true)
return true
} let pointer1 = 0
let pointer2 = 0 while (pointer2 < str2.length) {
if (str1[pointer1] === str2[pointer2]) {
pointer1++
pointer2++
} else {
pointer2++
} if (pointer1 >= str1.length) {
console.log(true)
return true
}
}
console.log(false)
return false
}isSubsequence('hello', 'hello Dear')
isSubsequence('book', 'brooklyn')
isSubsequence('abc', 'abc')
isSubsequence('', 'abc')-------------------
book => b => o => o => k => 超過範圍，停止，確認 book 為 brooklyn 的 Subsequence
brooklyn => b => r => o => o => k
Sliding(滑行) Window
是一種有名的演算法。
EX : [a, b, c, d, e, f, g, h]
Then, a sliding window of size 3 would run over it like
[a, b, c]
[b, c, d]
[c, d, e]
[d, e, f]
[e, f, g]
[f, g, h]Max and Min Sum
Write two functions that calculate the max and min sum of n consecutive(連續的) numbers in an arrayEX: maxSum([2, 7, 3, 0, 6, 1, -5, -12, -11],3) // 12
minSum([2, 7, 3, 0, 6, 1, -5, -12, -11],3) // -28---------------------------------------------[2, 7, 3, 0, 6, 1, -5, -12, -11]
[2, 7, 3]
[7, 3, 0]
[3, 0, 6]
[0, 6, 1]
[6, 1, -5]
[1, -5, -12]
[-5, -12, -11]for index0 to arr.length-n(看 n 設定多少，從最陣列最後往前推 n 格)---------------------------------------------每 3 個數字加總，最大的總和是多少function maxSum(arr, size) {
let max_value = -Infinity if (arr.length < size) {
console.log(null)
return null
} for (let i = 0; i <= arr.length - size; i++) {
let window = []
let tempSum = 0
for (let j = i; j < i + size; j++) {
window.push(arr[j])
tempSum += arr[j]
}
console.log(window)
if (tempSum > max_value) {
max_value = tempSum
}
} console.log(max_value)
return max_value
}maxSum([2, 7, 3, 0, 6, 1, -5, -12, -11], 3)-------------------------------------------每 3 個數字加總，最小的總和是多少function minSum(arr, size) {
let min_value = Infinity
if (arr.length < size) {
return null
}
for (let i = 0; i <= arr.length - size; i++) {
let attempt = 0
for (j = i; j < i + size; j++) {
attempt += arr[j]
}
if (attempt < min_value) {
min_value = attempt
}
}
console.log(min_value)
return min_value
}minSum([2, 7, 3, 0, 6, 1, -5, -12, -11], 3)
Max and Min sum
Write two functions that calculate the max and min sum of n consecutive(連續的) numbers in an arrayEX: maxSum([2, 7, 3, 0, 6, 1, -5, -12, -11],3) //12
minSum([2, 7, 3, 0, 6, 1, -5, -12, -11],3) //-28------------------------------[2, 7, 3]
[7, 3, 0]
重複的部分為 [7, 3]
因此下一輪只需要減掉 2 加上 0
就為新一輪的值------------------------------function maxSum(arr, size) {
if (size > arr.length) {
return null
} let max_value = 0
for (let i = 0; i < size; i++) {
max_value += arr[i]
} let temValue = max_value
for (let j = size; j < arr.length; j++) {
temValue = temValue + arr[j] - arr[j - size]
if (temValue > max_value) {
max_value = temValue
}
} console.log(max_value)
return max_value
}maxSum([2, 7, 3, 0, 6, 1, -5, -12, -11], 3)---------------------------------------------function minSum(arr, size) {
if (size > arr.length) {
return null
} let min_value = 0
for (let i = 0; i < size; i++) {
min_value += arr[i]
}
console.log(`min_value : ${min_value}`) let tem_min_vale = min_value
for (let j = size; j < arr.length; j++) {
tem_min_vale = tem_min_vale + arr[j] - arr[j - size]
if (tem_min_vale < min_value) {
min_value = tem_min_vale
}
}
console.log(tem_min_vale)
return tem_min_vale
}minSum([2, 7, 3, 0, 6, 1, -5, -12, -11], 3)
Min Subarray Length
Write a function called minSubLength which accept two parameters, an array of positive integers and a positive integer. This function should return minimal length of a continuous subarray - the sum of element insides this subarray has to be greater than or equal to the positeve integer parameter. If subarray not found, then return 0.EX : minSunLength([9, 8, 1, 4, 9, 5 ,1, 2], 11); // 2function minSubArray(arr, sum) {
let start = 0
let end = 0
let total = 0
let minLength = Infinity while (start < arr.length) {
if (total < sum && end < arr.length) {
total += arr[end]
end++
} else if (total >= sum) {
let currentLength = end - start
if (minLength > currentLength) {
minLength = currentLength
}
total -= arr[start]
start++
} else if (end >= arr.length) {
break
}
} if (minLength === Infinity) {
console.log('Cannot find the subarray that can sum up to the
given number')
return -1
} else {
console.log(minLength)
return minLength
}
}minSubArray([8, 1, 6, 15, 3, 16, 5, 7, 14, 30, 12], 60)
Unique Letters String
Write a function called uniqueLetterString, Which accepts a string and returns the length of the longest substring with all distinct characters.
function uniqueLetterString(str) {
let start = 0
let end = 0
let counter = {}
let maxLength = -Infinity while (end < str.length) {
console.log(counter)
if (counter[str[end]]) {
counter[str[start]]--
start++
} else if (!counter[str[end]]) {
counter[str[end]] = 1
end++
if (end - start > maxLength) {
maxLength = end - start
}
}
} if (maxLength === -Infinity) {
console.log('Cannot find unique letters substring.')
return null
}
console.log(maxLength)
return maxLength
}uniqueLetterString('thisishowwedoit')
Largest Product(乘積)
The four adjacent digits in the 100-digit number that have the greatest product are 9 x 9 x 8 x 9 = 5832.
Find the n adjacent digits in the 100-digit number that have greatest product. What is the value of this product?function largestProduct(n) {
let currentProduct
let maxProduct = -Infinity
let left = 0
let right = n - 1
while (right < thousandDigits.length) {
currentProduct = 1
for (let i = left; i <= right; i++) {
currentProduct *= thousandDigits[i]
}
if (currentProduct > maxProduct) {
maxProduct = currentProduct
}
right++
left++
}
console.log(maxProduct)
return maxProduct
}largestProduct(4)
Recursion(遞迴)
1. function 執行自己
2. 在遞迴中會使用到 stack 資料結構
3. 遞迴也是數學數列中的一種關係Recursive Sequence(Math)
T(1) = 10
T(n) = T(n-1)+15T : 10, 25, 40, 55
T(2) = T(2-1)+15 = T(1)+15 = 10+15=25
T(3) = T(3-1)+15 = T(2)+15 = T(1)+15+15 = 10+15+15 = 40
T(4) = T(4-1)+15 = T(3)+15 = T(2)+15+15 = T(1)+15+15+15 = 55Rseudocode of Recursive Sequence
RECURSION-SEQUENCE(n):
if n equals to 1:
return 10
else:
return RECURSION-SEQUENCE(n-1)+15---------------------------------------------function rs(n) {
console.log(`We are inside function rs(${n})`)
if (n === 1) {
return 10
} else {
return rs(n - 1) + 15
}
}console.log(rs(1))
console.log(rs(2))
console.log(rs(3))/*
rs(3) => return rs(2) + 15 but + 15 動作執行前 rs(2) 會先被執行
rs(2) => return re(1) + 15 but + 15 動作執行前 re(1) 會先被執行
rs(1) => return 10
====> 回到 rs(2)
rs(2) => return 10 + 15 = 25
====> 回到 rs(3)
re(3) => return 25 + 15 = 40
*/
Fibonacci Sequence
Write a function that takes an integer N as an input and returns the Nth number in Fibonacci SequenceFibonacci Sequence is defined by :
F(0)
F(1) = 1
F(n) = F(n-1) + F(n-1)-------------------------------------function fs(n) {
if (n === 0) {
return 0
} else if (n === 1) {
return 1
} else {
return fs(n - 1) + fs(n - 2)
}
}for (let i = 0; i < 10; i++) {
console.log(fs(i))
}
Array of Arrays
Write a function that collects all value in an array of arrays and return an array of values collected.let arrs = [[[["a", [["b", ["c"]], ["d"]]], [["e"]], [[["f", "g", "h"]]]]]]
collecter(arrs)// [a, c, c, d, e, f, g, h]----------------------------------------------let arrs = [[[["a", [["b", ["c"]], ["d"]]], [["e"]], [[["f", "g", "h"]]]]]];let result = []function collector(arr) {
for (let i = 0; i < arr.length; i++) {
if (Array.isArray(arr[i])) {
collector(arr[i])
} else {
result.push(arr[i])
}
}
}collector(arrs)
console.log(result)
Sorting Algorithms (排列演算法)
1. 排列演算法是在電腦科學中，基本且重要的演算法。
2. 在很多的現代程式語言中，本身都有內建 sorting functions，但仍需要知道演算法
是如何設計的。Bubble Sort
1. 泡沫排序會比較相鄰的元素，如果順序不對的話就會進行交換。
2. 泡沫排序是一個簡單的演算法，所以在現實中幾乎不會進行應用。[4, 7, 1, 2, 5, 3] => [4, 7, 1, 2, 3, 5] => [4, 7, 1, 2, 3, 5] =>
[4, 7, 1, 2, 3, 5] => [4, 1, 7, 2, 3, 5] => [1, 4, 7, 2, 3, 5] =>
[1, 4, 7, 2, 3, 5] => [1, 4, 7, 2, 3, 5] => [1, 4, 2, 7, 3, 5] =>
[1, 2, 4, 7, 3, 5] => [1, 2, 4, 7, 3, 5] => [1, 2, 4, 3, 7, 5] =>
[1, 2, 3, 4, 7, 5] => [1, 2, 3, 4, 5, 7]
(1). 1 47253
(2). 12 4753
(3). 123 475
(4). 1234 75
(5). 123457 Pseudocode of Bubble Sort
BUBBLE-SORT(A)
for i from 0 to A.length - 2(inclusive):
for j from A.length -1 to i + 1(inclusive):
if A[j] < A[j-1]:
exchange A[j] with A[j-1]---------------------------------------------function bubbleSort(arr) {
let step = 0
for (let i = 0; i <= arr.length - 2; i++) {
for (let j = arr.length - 1; j >= i + 1; j--) {
if (arr[j] < arr[j - 1]) {
let temp = arr[j]
arr[j] = arr[j - 1]
arr[j - 1] = temp
step++
}
}
}
console.log(step)
console.log(arr)
}let test = []
for (let i = 0; i < 100; i++) {
test.push(Math.floor(Math.random() * 100))
}bubbleSort(test)---------------------------------------------Overview of Bubble Sort
Worst Case Performance: O(n^2)
Best Case Performance: O(n)
Average Performance: O(n^2)---------------------------------------------Worst Case Performance: O(n^2)function bubbleSort(arr) {
let step = 0
for (let i = 0; i <= arr.length - 2; i++) {
for (let j = arr.length - 1; j >= i + 1; j--) {
if (arr[j] < arr[j - 1]) {
let temp = arr[j]
arr[j] = arr[j - 1]
arr[j - 1] = temp
step++
}
}
}
console.log(step)
console.log(arr)
}bubbleSort([5, 4, 3, 2, 1])
// n = 5
// 1/2 * n^2 - 1/2 * n^2
// 25/2 - 5/2 = 10---------------------------------------------Best Case Performance: O(n)function bubbleSort(arr) {
let step = 0
for (let i = 0; i <= arr.length - 2; i++) {
let swapping = false
for (let j = arr.length - 1; j >= i + 1; j--) {
if (arr[j] < arr[j - 1]) {
let temp = arr[j]
arr[j] = arr[j - 1]
arr[j - 1] = temp
step++
swapping = true
console.log(arr)
}
}
if (swapping === false) {
break
}
}
console.log(step)
console.log(arr)
}bubbleSort([1, 2, 3, 4, 0, 5, 6, 7])
Insertion Sort
實際上的運作效率比 bubble sort 好一些，但理論是彼此的 Big O value 是相同的(O(n^2))。
此演算法會不斷地將 value 插入到排列好的 array 中。Pseudocode of Insertion Sort
INSERTION-SORT(A):
for j from index 1 to A.length -1(inclusive):
key = A[j]
// Now, insertion key into the sorted sequence A[0, 1, 2..., j
- 1]
i = j - 1
while i >=0 and A[i] > key:
A[i + 1] = A[i]
i = i - 1
A[i + 1] = key-------------------------------index 0, 1, 2, 3, 4
value 1, 2, 3, 4, 0key = 0
i(index) = 3while i >=0 A[i]>key:
A[i+1] = A[i]
i -= 1
index 0, 1, 2, 3, 4
value 1, 2, 3, , 4key = 0
i = 2while i >=0 A[i]>key:
A[i+1] = A[i]
i -= 1
index 0, 1, 2, 3, 4
value 1, 2, , 3, 4key = 0
i = 1while i >=0 A[i]>key:
A[i+1] = A[i]
i -= 1
index 0, 1, 2, 3, 4
value 1, , 2, 3, 4key = 0
i = 0while i >=0 A[i]>key:
A[i+1] = A[i]
i -= 1
index 0, 1, 2, 3, 4
value , 1, 2, 3, 4key = 0
i = -1while i >=0 A[i]>key:
A[i+1] = A[i]
i -= 1
A[i+1] = key
index 0, 1, 2, 3, 4
value 0, 1, 2, 3, 4---------------------------------------------let unsorted = [14, -4, 17, 6, 22, 1, -5]function insertionSort(arr) {
for (let j = 1; j <= arr.length - 1; j++) {
let key = arr[j]
i = j - 1
console.log(`key : ${key}`)
while (i >= 0 && arr[i] > key) {
arr[i + 1] = arr[i]
i -= 1
}
arr[i + 1] = key
console.log(arr)
}
console.log(arr)
}insertionSort(unsorted)---------------------------------------------Overview of Bubble Sort
Worst Case Performance: O(n^2)
Best Case Performance: O(n)
Average Performance: O(n^2)
Selection Sort
原則是不斷的從尚未排序好的 array 中找到最小的值，並與未排序完成的 array 最左邊的值進行交換。
選擇排序法是一個不有效的排序法(O(n^2))selection 的意思為找到 array 中最小的 element，並進行互換
[5, 1, 3, 2, 7, 4] => [1, 5, 3, 2, 7, 4] => [1, 2, 3, 5, 7, 4] =>
[1, 2, 3, 5, 7, 4] => [1, 2, 3, 4, 7, 5] => [1, 2, 3, 4, 5, 7]---------------------------------------------
Pseudocode of Finding the Smallest Value
SMALLEST-VALUE(A):
smallest = A[0]
for i from i to A.length -1:
if A[i] < smallest:
smallest = A[i]
return smallest
---------------------------------------------
Pseudocode of Selection Sort
SELECTION-SORT(A):
for i from 0 to A.length -2:
minIndex = i
for j from i to A.length-1:
if A[j] < A[minIndex]:
minIndex = j
swap A[minIndex] and A[i]---------------------------------------------let unsorted = [14, -4, 17, 6, 22, 1, -5]function selectionSort(arr) {
for (let i = 0; i <= arr.length - 2; i++) {
let minIndex = i
for (let j = i; j <= arr.length - 1; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j
}
}
// swap arr[minIndex] and arr[i]
let tem = arr[minIndex]
arr[minIndex] = arr[i]
arr[i] = tem
console.log(arr)
}
console.log(arr)
return arr
}selectionSort(unsorted)---------------------------------------------Overview of Selection Sort
Worst Case Performance: O(n^2)
Best Case Performance: O(n^2)
Average Performance: O(n^2)
Sorting Algorithms (排列演算法) II
Merge Sort
- 原則是善用一個事實，合併兩個排序好的陣列的時候，是 O(n) 的時間複雜度。
Pseudocode I of Merge Sort
MERGE(A1, A2): (備註 : A1, A2 為排列好的陣列)
result = [], i = 0, j = 0
while i < A1.length and j < A2.length:
if A1[i] > A2[j]:
add A2[j] to result
j++
else
add A1[i] to result
i++
// 不論是 A1 or A2 有元素留下來
// 需要將剩下的元素都放入 result 中-----------------------------------------------Pseudocode II of Merge Sort
MERGE-SORT(A):
if A.length equals to 1:
return A
else : (備註 : divide and conquer)
middle = A.length/2
left = A.slice(0, middle)
right = A.slice(middle, A.length)
return MERGE(MERGE-SORT(rigth),MERGE-sort(left))-------------------------------------------------
function merge(a1, a2) {
let result = []
let i = 0
let j = 0 while (i < a1.length && j < a2.length) {
if (a1[i] > a2[j]) {
result.push(a2[j])
j++
} else {
result.push(a1[i])
i++
}
}
// a1 or a2 might have some elements left
// use loop to put them all into result
while (i < a1.length) {
result.push(a1[i])
i++
}
while (j < a2.length) {
result.push(a2[j])
j++
}
return result
}
function mergeSort(arr) {
if (arr.length === 1) {
return arr
} else {
let middle = Math.floor(arr.length / 2)
let left = arr.slice(0, middle)
let right = arr.slice(middle, arr.length)
return merge(mergeSort(right), mergeSort(left))
}
}console.log(mergeSort([1, 3, 2, 4]))
Tree (Data Structure)
在電腦科學中，Tree 是被廣泛使用的抽象資料類型，被用來模擬分層的樹狀結構。
- 每一個 tree 中只能有一個 root
- tree 是一個沒有循環的資料結構
Binary Tree
- 二元樹中的每一個節點，最多只能有兩個子節點，稱為左子節點、右子節點
Heap Sort
- Heap Sort 會使用到 Max Heap 來排序
- 為了要理解 Heap Sort，需要知道 Max Heap 的運作原理How to create Max Heap?
- When we swap a node N down, just keep swapping if the node N has a child node that is biggest than the node N.Array = [6,13,10,4,1,5,2,8,14,9,11,7,3,15,12]
MaxHeap = [15,14,12,13,11,7,10,8,4,9,4,9,1,5,3,2,6]
Heap Sort
Pseudocode of Build Max Heap
BUILD-MAX-HEAP():
heapSize = A.length-1
for i from (A.length/2) to 0(inclusive):
MAX-HEAPIFY(i)
Pseudocode of Max Heapify
Max-HEAPIFY(i):
left = 2 * i + 1
right = 2 * i + 2
if left <= heapSize and A[left] > A[i]:
largest = left
else:
largest = i
if right <= heapSize and A[right] > A[largest]:
largest = r
if largest is not i:
swap A[i] with A[largest]
MAX-HEAPIFT(largest)
Pseudocode of Heap Sort
HEAP-SORT():
BUILD-MAX-HEAP() (備註 BT => MH)
for i from A.length -1 to 0:
exchange A[0] with A[i]
heapSize = heapSize - 1
MAX-HEAPIFY(0)