Big O

  • Time Complexity: measure in number of operation, how much time it cost
  • Space Complexity: memory usage

Omega(Ω), Theta(Θ) & Omicron(Ｏ)

  • Omega is the fastest case.
  • Theta is the average case.
  • Omicron is the slowest case.

Big O always measuring the worst (slowest) case.

Drop Non-Dominants

O(n^2 + n) === O(n^2)

後面的 n 對複雜度等級影響不大，所以省去不寫

Terms

  • O(n^2): loop with a loop
  • O(n): proportional
  • O(log n): divide and conquer
  • O(1): constant

Tree

  • divide and conquer

Hashtable

Characteristics of Hashtable

  1. One way
  2. Deterministic

Concepts

  • Collision
  • Separate chaining
  • Linear probing (open addressing)

Graph

Tree is a graph, linked list is also a graph.

  • Adjacency matrix
  • Adjacency list

Heap

  • Heap always be complete.
  • Root node should be maximum or minimum value. It is called maximum heap or minimum heap respectively.
  • Every parent node’s value should be greater than its children node.
  • Store heap data in one-dimensional array.
  • Root node is stored at second position, namely, at index equals to 1.
leftChildIndex = 2 * parentIndex
rightChildIndex = 2 * parentIndex + 1
parentIndex = floor(childIndex / 2)

Recursion

A function that calls itself, until it doesn’t.

Two Case in Recursion

  • Base case (recursion terminate condition)
  • Recursive case (calling itself)

Call Stack

Stack: Last in, first out. (LIFO)

Factorial

function factorial(num: number): number {
  if (num === 1) return 1;
  else return num * factorial(num - 1);
}

Sorting

Bubble Sort

Selection Sort

Insert Sort

Merge Sort

Quick Sort

Dynamic Programming

  • Overlapping subproblems
  • Optimized substructure