CS5800 notes

week 1

1.1 linear/chunk/binear search

这三种方法都是有序查找使用的

chunk

分割成一堆block，每一个block都是一个linear

Chunk的复杂度 $O(\frac{n}{c} + c)$,把所有的循环都走一边，再走一遍步长。

让$O(\frac{n}{c} + c)$尽可能的小，也就是$\frac{n}{c}$ == $c$

最终得到时间复杂度为 $O(\sqrt{n})$

binary

经典二分

时间复杂度用递归法(recursive algorithm)，
$T(n) = T(\frac{n}{2})+1 , T(1) = 1$
最终为 $O(log_2n)$

1.2

• Linear time ep. $O(1)$
• Logarithmic time ep. $O(logn)$
• Polynamial time ep. $O(n^1+n^2+n^3)$
• Exponential time ep. $$O(2^n)$$
• factorial time ep. $O(n!)$ 5! = 5x4x3x2x1

不考虑constants

• big-$O$ : upper bound
• big-$\Omega$ : lower bound
• big-$\Theta$ : tight bound

lecture

• efficiency Time and Space 消耗
• effectiness 证明是对的