跳到內容
inorisense
關於我 數位花園
部落格

Udemy Javascript Data Structures and Algorithms

Big O

Section titled “Big O”
  • Time Complexity: measure in number of operation, how much time it cost
  • Space Complexity: memory usage

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

Section titled “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

Section titled “Drop Non-Dominants”
O(n^2 + n) === O(n^2)

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

Terms

Section titled “Terms”
  • O(n^2): loop with a loop
  • O(n): proportional
  • O(log n): divide and conquer
  • O(1): constant

Binary Tree

Section titled “Binary Tree”

Terminology

Section titled “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

Section titled “Ref”

Hashtable

Section titled “Hashtable”

Characteristics of Hashtable

Section titled “Characteristics of Hashtable”
  1. One way
  2. Deterministic

Concepts

Section titled “Concepts”
  • Collision
  • Separate chaining
  • Linear probing (open addressing)

Graph

Section titled “Graph”

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

  • Adjacency matrix
  • Adjacency list

Heap

Section titled “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

Section titled “Recursion”

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

Two Case in Recursion

Section titled “Two Case in Recursion”
  • Base case (recursion terminate condition)
  • Recursive case (calling itself)

Call Stack

Section titled “Call Stack”

Stack: Last in, first out. (LIFO)

Factorial

Section titled “Factorial”
function factorial(num: number): number {
  if (num === 1) return 1;
  else return num * factorial(num - 1);
}

Sorting

Section titled “Sorting”

Bubble Sort

Section titled “Bubble Sort”

Selection Sort

Section titled “Selection Sort”

Insert Sort

Section titled “Insert Sort”

Merge Sort

Section titled “Merge Sort”

Quick Sort

Section titled “Quick Sort”

Dynamic Programming

Section titled “Dynamic Programming”
  • Overlapping subproblems
  • Optimized substructure