Published on

Math for algorithms

Authors

Math basics for algorithm

A.1 求和公式及其性质

  • 等差 ∑k=1nk=n(n+1)2\sum_{k=1}^n k = \frac{n(n+1)}{2}
∑k=1nk2=n(n+1)(2n+1)6\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6} ∑k=1nk3=n2(n+1)24\sum_{k=1}^n k^3 = \frac{n^2(n+1)^2}{4}
  • 线性性质
∑k=1n(cak+bk)=c∑k=1nak+∑k=1nbk\sum_{k=1}^n (ca_k+b_k) = c\sum_{k=1}^n a_k + \sum_{k=1}^n b_k ∑k=1nΘ(f(k))=Θ(∑k=1nf(k))\sum_{k=1}^n \Theta\left(f(k)\right) = \Theta \left( \sum_{k=1}^n f(k) \right)
  • 几何级数
∑k=0nxk=1+x+x2+…+xn=xn+1−1x−1\sum_{k=0}^n x^k = 1 + x + x^2 + \ldots + x^n = \frac{x^{n+1} - 1}{x - 1} ∑k=0∞xk=1x−1\sum_{k=0}^{\infty} x^k = \frac{1}{x - 1}
  • 调和级数
Hn=1+12+13+14+…+1n=∑k=1n1k=ln⁡n+O(1)H_n = 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \ldots + \frac{1}{n} = \sum_{k=1}^n \frac{1}{k} = \ln{n} + O(1)
  • 级数积分与微分
∑k=0∞kxk=x(1−x)2\sum_{k=0}^{\infty} kx^k = \frac{x}{(1-x)^2}
  • 列项级数 telescopes
∑k=1n(ak−ak−1)=an−a0\sum_{k=1}^{n} (a_k - a_{k-1}) = a_n - a_0 ∑k=0n−1(ak−1−ak)=a0−an\sum_{k=0}^{n-1} (a_{k-1} - a_k) = a_0 - a_n ∑k=1n−11k(k+1)=∑k=1n−1(1k−1k+1)=1−1n\sum_{k=1}^{n-1} \frac{1}{k(k+1)} = \sum_{k=1}^{n-1} \left(\frac{1}{k} - \frac{1}{k+1}\right) = 1 - \frac{1}{n}
  • 乘积 lg⁡(∏k=1nak)=∑k=1nlg⁡ak\lg\left(\prod_{k=1}^{n} a_k \right) = \sum_{k=1}^{n} \lg{a_k}

A.2 确定求和时间的界

  • 数学归纳法

  • 确定级数中各项的界

  • ∑k=1∞1k=lim⁡n→∞∑k=1n1k=lim⁡n→∞Θ(lg⁡n)=∞\sum_{k=1}^{\infty} \frac{1}{k} = \lim_{n \to \infty} {\sum_{k=1}^{n} \frac{1}{k}} = \lim_{n \to \infty} {\Theta(\lg n)} = \infty
Hn=∑k=1n1k=1+12+13+14+…+1n≤ln⁡n+1H_n = \sum_{k=1}^n \frac{1}{k} = 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \ldots + \frac{1}{n} \leq \ln{n} + 1

  • 通过积分求和的近似

    • if f(x)f(x) 单调递增:

      ∫m−1nf(x) dx≤∑k=mnf(k)≤∫mn+1f(x) dx \int_{m-1}^{n} f(x)\,dx \leq \sum_{k=m}^n f(k) \leq \int_{m}^{n+1} f(x)\,dx

    • if f(x)f(x) 单调递减:

      ∫mn+1f(x) dx≤∑k=mnf(k)≤∫m−1nf(x) dx \int_{m}^{n+1} f(x)\,dx \leq \sum_{k=m}^n f(k) \leq \int_{m-1}^{n} f(x)\,dx
    Hn=∑k=1n1k≥∫1n+11x dx=ln⁡(n+1)H_n = \sum_{k=1}^n \frac{1}{k} \geq \int_{1}^{n+1} \frac{1}{x}\,dx = \ln{(n+1)} ∑k=2n1k≤∫1n1x dx=ln⁡(n)\sum_{k=2}^n \frac{1}{k} \leq \int_{1}^{n} \frac{1}{x}\,dx = \ln{(n)} Hn=∑k=1n1k≤ln⁡n+1H_n = \sum_{k=1}^n \frac{1}{k} \leq \ln{n} + 1

重点

  • Illustrate function call stack

  • Describe how to convert recursion to iteration

    • one function call

    • 2 or more function calls

    • tail recursion

  • PERMUTATION

PERM(A, k)
  if(k == n)
    PRINT(A)
  for i = 1 to n
    SWAP(A, i, k)
    PERM(A, k+1)
    SWAP(A, i, k)

PERM(A, 1)

  • DFS and stack

  • BFS and queue

Discuss on Twitter • View on GitHub