算法基础笔记0x01 —— 算法分析

focus on speed

时间复杂度

  • Time complexiy of algorithm is number of steps it takes before it terminates.
    • 在算法终止之前操作的步数
  • Issue 1: Number of steps depends on input size
    • Analyze complexity as a function of input size
  • Issue 2: Even for a fixed size, the running time can vary
    • Consider worst case
    • Sometimes we consider average case
      • but we don’t know how the input are distributed
  • Issue 3: What counts as a step?
    • Eg: check for a word. Step is checking one word or a page.
    • we need to user a coarse-grained model, ignore minor details and focus on big picture.
    • 此处粗粒度模型,可简单理解为将复杂系统简化

程序结构分析

for循环 (可嵌套)

  • counts all “stuff” done in the innermost loop as one step
    • stuff doesn’t change with n
  • Step complexity is n.

     
  • Step complexity is $\lceil{\frac{n}{2}}\rceil$.

     
  • $n*2n = 2n^2$ iterations / steps

     
  • Number of iterations = numberof *’s printed = $\frac{n(n-1)}{2}

     

while循环

  • n steps / iteration
  • $\lceil{log_2{n}}\rceil$ steps / iteration

if-else语句

  • Assume the longest branch gets run
  • Complexity is the number of steps in longest branch
  • $n^2 \geq n$, so step complexity is $n^2$

递归方程

  • Functions call themselves to solve ‘self reducible’ problems
    • ‘self reducible’: we can solve the problem by first solving smaller instances of the problems

Several solutions to recurrence relation:

  • Solve it directly, e.g. based on a guess.
  • Substitution method.
  • Recursion tree.
  • Master method.

前三种方法需要用数学归纳法证明结果的正确性

  • Eg1: S(n) = 1 + S(n-1)

    • Base case S(1) = 1, since we just do return when n = 1.
    • For n > 1, we do one step (+), then call sum(n-1), which takes S(n-1) steps.
  • Eg2: S(n) = n + S(n-2)

    • Base case S(0) = S(1) = 1.
    • For n > 1, we do n steps in the for loop. Then we call foo(n-2), which takes S(n-2) steps.

递归方程的四种解决方法

Directly Solving

  • eg1: $S(n) = 1 + S(n-1)$, $S(1) = 1

    • $S(2) = 2$, $S(3) = 3$, $S(4) = 4$, so we guess $S(n) = n$.
    • Induction:
      • Base case: $S(1) = 1$
      • $S(n) = 1 + S(n-1) = n-1 + S(1) = n$
  • eg2: $S(n) = n + S(n-2)$, $S(0) = S(1) = 1$.

    • $S(1) = 1$, $S(3) = 4$, $S(5) = 9$, $S(7) = 16$, so we guess $S(n) = S(2m-1) = m^2 = (n+1/2)^2$.
    • Induction:
      • Base case: $S(1) = 1 = 1^2$
      • $S(n+2) = S(2(m+1)-1) = n + 2 + S(n)$
      • $= 2m + 1 + m^2 = (m+1)^2$

Substitution Method

和直接求解很接近,将S(n)根据公式代为S(n-1)的表达式,继续替代直至代为含S(1)的表达式。

Recursion Tree

以上两个方法,都需要有一个好的猜测,我们可以从递归树中来找到这个good guess.

  • Each level does n work, so total work is $S(n) = n*log_2{n}$

Master Method

  • Master theorem, 主定理
  • [Introduction to Algorithms] Theorem 4.1(Master theorem)

Let $a\geq 1$ and $b>1$ be constants, let $f(n)$ be a function, and let $T(n)$ be defined on the nonnegative integers by the recurrence $$T(n) = aT(n/b) + f(n)$$
where we interpret $n/b$ to mean either $\lfloor{n/b}\rfloor$ or $\lceil{n/b}\rceil$. Then $T(n)$ has the following asymptotic bounds:

  1. If $f(n) = O(n^{log_b{a-\epsilon}})$, for some constance $\epsilon > 0$, then $T(n) = \Theta(n^{log_b{a}})$.
  2. If $f(n) = \Theta(n^{log_b{a}})$, then $T(n) = \Theta(n^{log_b{a}}lg{n})$.
  3. If $f(n) = \Omega(n^{log_b{a+\epsilon}})$, for some constance $\epsilon > 0$, and if $af(n/b)\leq cf(n)$ for some constance $c<1$ and all sufficiently large $n$, then $T(n)=\Theta(f(n))$.

Mater theorem caveats

  • Note that in cases 1 and 3, $f(n)$ needs to be smaller/larger than $n^{log_b{a}}$ by a polynomial factor $n^\epsilon$.
  • So we can’t always apply Master theorem.

Notations

Ideas

  • 对于输入量大的函数比较,短期表现并不重要,我们关心函数的长期表现。
  • 我们忽略常数因数的差别,即n, 2n, 100n, 0.01n全部都是同样大小。

Five Operators

Big O Pictorially

Big O Properties

  • If $f(n)=O(g(n))$ and $f(n)=\Omega(g(n))$, then $f(n)=\Theta(g(n))$.
  • $O$, $\Omega$, $\Theta$是可传递的。
  • $\Theta$是对称的,即$f(n)=\Omega(g(n))$,那么$g(n)=\Omega(f(n))$。
  • $O(1)$是常数的集合。any $c = O(1)$

2 Replies to “算法基础笔记0x01 —— 算法分析”

Leave a Reply

Your email address will not be published.