# algorithm & data structure (JS)

## Big O Analysis

best ----> worst
1 < logn < sqrt(n) < nlogn < n^(2) < n^(3) ... < 2^(n) < 3^(n) ... < n^(n)

### Objects
Insertion -> O(1)
Removal -> O(1)
Searching -> O(n) (視乎object大小)
Accessing -> O(1) 每個 obj 跟 arr 的所需時間是一樣的，因為是 **Hash Tables** 形態的原因，這會在後續補充解釋。

### Array
Inservation
- push(從尾巴新增) -> O(1)
- unshift(從開始位置新增) -> O(n) 因為會動到 index number

let n=5
let arr = [1,2,3,4]

for (let i=0; i<n; i++) {
    arr.push(10)
}
// 此時 big O 為 O(n)

for (let i=0; i<n; i++) {
    arr.unshift(10)
}
// 此時 big O 為 O(n^(2))，即便看起來都是只有一個 for loop，但 arr.unshift 已有一個 O(n)，因此會是 n^(2)

Removal
- pop(從尾刪) -> O(1)
- shift(從頭刪) -> O(n)

Searching -> O(n)
Accessing -> O(1)

## Algorithm Design
### 1. Linear Search (Sequential Search)
兩個條件停止搜尋
1)until a match is found
2)whole list has been searched

    let arr1 = [1,3,5....,n]

    function linear(arr, n) {
      for(let i=0; i <= arr.length; i++) {
        if(arr[i] === n) return `${n} at index ${i} of array `
      }
      return 'Not found'
    }

    linear(arr1, n)

Performance:
Worst Case -> O(n) *最大值*
Best Case -> O(1) *array第一筆*
average performance -> O(n/2)

### 2. Binary Search
Bianary 又是二進制的意思
只能在 sorted array 下運用，一直往中間數切

    function binarySearch(arr, num) {
      let min = 0
      let max = arr.length-1

      while(min <= max) {
        let middle = Math.floor((max+min)/2)
        if (num > arr[middle]) {
          min = middle+1
        } else if (num < arr[middle]) {
          max = middle-1
        } else {
          console.log(`find number ${num} at position ${middle}, totel step: ${step}`)
          return middle
        }
      }
      return -1
    }

Performance:
Worst Case -> O(logn) **<- form f(n)=log₂n*
Best Case -> O(1) *sored array的正中央*
average performance -> O(logn)

### 3. Counter
常見的技巧 （general skill)
A counter object will reduce the complexity of algorithms

**Intersection 找出重複值**
Without Counter -> O(n^2) because of double for loop

    // O(n^2)
    function intersectionWithoutCounter(array1, array2, finalArray) {
      for(let i=0; i<array2.length; i++) {
        for(let j=0; j<array1.length; j++) {
          if(array1[j] == array2[i]) {
            finalArray.push(array1[j])
          }
        }
      }
      console.log(finalArray.sort((a, b) => {return a-b}))
    }

With Counter -> O(n)
計算每個值出現的次數，將次數大於 1 的印出

    function intersectionWithCounter(array1, array2) {
      let arr3 = array1.concat(array2)
      let count = {}
      for(let i=0; i<arr3.length; i++) {
        if(!count[arr3[i]]) {
          count[arr3[i]] = 1
        } else {
          count[arr3[i]] ++
        }

      }
      for(key in count) {
        if(count[key] > 1) {
          console.log(key)
        }
      }
    }

### 4. Pointer
有不同的稱呼名字但idea一樣，用於 reduce the complexity of algorithms
例子 averagePair(arr, num)，num是平均值，將 array 的值從頭到尾相加一次，若兩個數值相加除2等於平均值，記錄兩個數值
e.g. averagePair([-11,0,1,2,3,14,88],1.5) -> -11跟14、0跟3、1跟2

function averagePair(arr, num) {
  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 == num) {
        result.push(arr[i]}","arr[j])
      }
    }
  }
  console.log(result)
}

以上是沒使用 Pointer，使用兩個 for loop，因此為 O(n^2)，接下來使用 Pointer

function averagePairWithPointer(arr, num) {
  let result = []
  let left = 0;
  let right = arr.length-1
  
  while(right > left) {
    let average = (arr[left]+arr[right])/2
    console.log(`left: ${arr[left]}, right: ${arr[right]}, average: ${average}`)
    if(average > num) {
      right--
    } else if(average < num) {
      left++
    } else if(average == num) {
      result.push(arr[left]+","+arr[right])
      right--
      left++
    }
  }
  console.log(result)
}

其運算方式為，比對Sorted Array 最前值 && 最後值相加並除以 2，若大於平均值，最後值往前移一個；若小於則最前值往後移一個，最終兩個數經過推算會碰到，While loop就結束～

Pointer practice: palindrome(string的正順序及反順序是否一致)

function isPalindrome(str) {
  let left=0
  let right=str.length-1
  
  while(right > left) {
    if(str[left] !== str[right]) return false
    // console.log(`left: ${str[left]}, right: ${str[right]}`)
    left++
    right--
  }
  return true
}

Pointer Practice2: subsequence problem，比對兩個 Array，分別是 Main Array跟 Sub Array，按著順序由左到右看，只要 Main Array 有出現在 Sub Array 過，即便中間有其他字，都一律接受
例子：`// ("bye","byze") 跟 ("frank","frjanlk")` 都會回傳 true，前者跳過"y"最終也會組成"bye"，後者跳過中間的"j"跟"l"，最終也會組成"frank"，但若是 `("abc","cba")`，就不一樣囉，因為按順序來說它是"cba"，而非"abc"，因此回傳 false。

function isSubsequence(mainStr, subStr) {
  if (mainStr.length === 0) return  true
  let arr = mainStr.split("")
  let cArray = [] //comparisonArray
  let main=0
  let sub=0

  while(sub < subStr.length) {
    console.log(`mainStr: ${mainStr[main]}, subStr: ${subStr[sub]}`)
    if(mainStr[main] === subStr[sub]) {
      cArray.push(mainStr[main])
      main++
      sub++
    } else {
      sub++
    }
  }
  if (cArray.length !== arr.length) return false
  if (JSON.stringify(cArray) !== JSON.stringify(arr)) return false
  return true
}

上述是一開始自己的做法，但仔細查看會發現，其實不用等全部跑完再用 stringify 的方式做比對，以下是更簡潔的方式：

function isSubsequenceUdemy(str1, str2) {
  if(str1.length === 0) return true
  let pointer1 = 0
  let pointer2 = 0

  while(pointer2 < str2.length) {
    if(str1[pointer1] === str2[pointer2]) pointer1++
    if(pointer1 > str1.length-1) return true
    pointer2++
  }
  return false
}

只要滿足 pointer1 的長度(length) 等於 str1 的長度，就可以 return true，某則一律 false

### 5. Sliding Window
滑行的視窗

### 6. Recursion 遞回