算法基础笔记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$

Recursion Tree

• 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全部都是同样大小。

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)$