算法设计与分析笔记0x00 —— 课程介绍及基础知识

此系列算法设计笔记基于 ShanghaiTech CS240 Fall2017 算法设计与分析课程。
相较算法基础课程,更加偏向于数学分析。
computational tractability: 计算的可追踪性,即可用数学语言进行推理证明

Notation Properties

算法导论的笔记中提到了其可传递性,在这里补充上可加性。

  • If f = O(h) and g = O(h) then f + g = O(h).
  • If f = Ω(h) and g = Ω(h) then f + g = Ω(h).
  • If f = Θ(h) and g = O(h) then f + g = Θ(h).

Asymptotic Bounds for Some Common Functions

  • Polynomial: $a_0+a_1 n+…+a_d n^d$ is $\Theta(n^d)$ if $a_d>0$.
  • Logarithms: $O(log_a{n})=O(log_b{n})$ for any constants $a, b > 0$.
  • Logarithms: For every $x>0$, $logn=O(n^x)$.
    • log增长慢于所有多项式
  • Exponentials: For every $r>1$ and every $d>0$, $n^d=O(r^n)$.

常见算法的复杂度分析

  • $O(n)$: 找出a1,a2,…,an最大值

     
  • $O(n)$: 合并两个已排好序的列表(A = a1,a2,…, an; B = b1, b2,…, bn)

     
  • $O(nlogn)$: divide and conquer, like mergesort and heapsort
  • $O(n^2)$: 在(x1,y1),…(xn,yn)中找到最近的一对点

     
  • $O(n^3)$: 给定n个集合S1,…,Sn, 找出disjoint的每对集合

     
  • $O(n^k)$: 找出图中的大小为k的独立集

    • $C_{n}^{k} = \frac{n(n-1)(n-2)…(n-k+1)}{k(k-1)(k-2)…(2)(1)}\leq\frac{n^k}{k!}$

 

  • $O(n^2 2^n)$: 给定一个图,求出最大的独立集

     

Course Structure

  • Graph algorithms
  • Greed
  • Divide-and-conquer
  • Dynamic programming
  • Network flow
  • Intractability (complexity classes)
  • Coping with intractability
  • Approximate algorithms
  • Randomized algorithms
  • Local search

Leave a Reply

Your email address will not be published.