算法通关40讲

Big O notation

O(1): Constant Complexity（常数复杂度）
O(log n): Logarithmic Complexity（对数复杂度）
O(n): Linear Complexity（线性时间复杂度）
O(n^2): N square Complexity（平方）
O(n^3): N square Complexity（立方）
O(2^n): Exponential Growth（指数）
O(n!): Factorial（阶乘）

Big O Poster

Array

复杂度分析

Access:  O(1)
Insert: 平均O(n)，如果插入到最后一个则是O(1)
Delete: 平均O(n)，如果删除最后一个则是O(1)

Linked List

Doubly Linked List

复杂度分析

space:   O(n)
prepend: O(1)
append:  O(1)
lookup:  O(n)
insert:  O(1)
delete:  O(1) 

Stack - First In First Out (FIFO)
Queue - First In Last Out (FILO)

Stack - First In First Out (FIFO)
Queue - First In Last Out (FILO)
PoriorityQueue - 优先队列

实现机制

1. Heap (Binary, Binomial, Fibonacci)
2. Binary Search Tree

两种堆

1. 小顶堆
2. 大顶堆

1. Hash Function
2. Hash Collisions

Linked List 就是特殊化的 Tree
Tree 就是特殊化的 Graph

TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;
    TreeNode left = lowestCommonAncestor(root.left, p, q);
	TreeNode right = lowestCommonAncestor(root.right, p, q);
	return left == null ? right : right == null ? left : root;
}

def lowestCommonAncestor(self, root, p, q):
    if p.val < root.val > q.val:
        return self.lowestCommonAncestor(root.left, p, q)
    if p.val > root.val < q.val:
        return self.lowestCommonAncestor(root.right, p, q)
    return root

def lowestCommonAncestor(self, root, p, q):
    while root:
        if p.val < root.val > q.val:
            root = root.left
        elif p.val > root.val < q.val:
            root = root.right
        else:
            return root        

前序（Pre-order）根-左-右
中序（In-order）左-根-右
后序（Post-order）左-右-根

def preorder(self, root):
    if root:
        self.traverse_path.append(root.val)
        self.preorder(root.left)
        self.preorder(root.right)
        
def inorder(self, root):
    if root:
        self.inorder(root.left)
        self.traverse_path.append(root.val)
        self.inorder(root.right)
        
def postorder(self, root):
    if root:
        self.postorder(root.left)
        self.postorder(root.right)
        self.traverse_path.append(root.val)

Recursion

def recursion(level, param1, param2, ...):
    # recursion terminator
    if level > MAX_LEVEL:
        print_result
        return
    
    # process logic in current level
    pocess_data(level, data...)
    
    # drill down
    self.recursion(level + 1, p1, ...)
    
    # reverse the current level status if needed
    reverse_state(level)

Divide & Conquer

def divide_conquer(problem, param1, param2, ...):
    
    # recursion terminator
    if problem is None:
        print_result
        return
    
    # prepare data
    data = prepare_data(problem)
    subproblems = split_problem(problem, data)
    
    #conquer subproblems
    subresult1 = self.divide_conquer(subproblems[0], p1, ...)
    subresult2 = self.divide_conquer(subproblems[1], p1, ...)
    subresult3 = self.divide_conquer(subproblems[2], p1, ...)
    ...
    
    # process and generate the final result
    result = process_result(subresult1, subresult2, subresult3, ...)

How a BFS Would Traverse This Tree

def BFS(graph, start, end)
    
    queue = []
    queue.append([start])
    visited.add(start)
    
    while queue:
        node = queue.pop()
        visited.add(node)
        
        process(node)
        nodes = generate_related_nodes(node)
        queue.push(nodes)
        
    # other processing work

How a DFS Would Traverse This Tree

BFS vs DFS

DFS 递归写法

visited = set()
def dfs(node, visited):
    visited.add(node)
    # process current node here.
    ...
    for next_node in node.children():
        if not next_node in visited:
            dfs(next_node, visited)            

DFS 非递归写法

def DFS(self, tree):
    
    if tree.root is None:
        return []
    
    visited, stack = [], [tree.root]
    
    while stack:
        node = stack.pop()
        visited.add(node)
        
        process(node)
        nodes = generate_related_nodes(node)
        stack.push(nodes)
        
    # other processing work
    ...

三个要点：

1. Least Recently Used
2. Hash Table + Double LinkedList
3. O(1) get and O(1) set

常用两种：

1. LFU - least frequently used

1. LRU - least recently used

两个特点：

1. 空间效率和查询速度远超一般算法
2. 查询不存在肯定不存在
3. 查询存在但不一定存在，需要再次确认
4. 查询不存在肯定不存在情况

• 查询存在但不一定存在情况