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

Binary Tree

Terminology

  • Nodes: The fundamental part of a binary tree, where each node contains data and link to two child nodes.
  • Root: The topmost node in a tree is known as the root node. It has no parent and serves as the starting point for all nodes in the tree.
  • Parent Node: A node that has one or more child nodes. In a binary tree, each node can have at most two children.
  • Child Node: A node that is a descendant of another node (its parent).
  • Leaf Node: A node that does not have any children or both children are null.
  • Internal Node: A node that has at least one child. This includes all nodes except the root and the leaf nodes.
  • Depth of a Node: The number of edges from a specific node to the root node. The depth of the root node is zero.
  • Height of a Binary Tree: The number of nodes from the deepest leaf node to the root node.
  • “full” tree: every node has 0 or 2 children.
  • “perfect” tree: all internal nodes have 2 children and all leaf nodes are at the same level.
  • “complete” tree: the last level element are stored in left to right order

Ref

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