CS5800 notes

week 1

1.1 linear/chunk/binear search

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

chunk

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

Chunk的复杂度 $$,把所有的循环都走一边，再走一遍步长。

让$$尽可能的小，也就是$$ == $$

最终得到时间复杂度为 $$

binary

经典二分

时间复杂度用递归法(recursive algorithm)，
$$
最终为 $$

1.2

• Linear time ep. $$
• Logarithmic time ep. $$
• Polynamial time ep. $$
• Exponential time ep. $$
• factorial time ep. $$ 5! = 5x4x3x2x1

不考虑constants

• big-$$ : upper bound
• big-$$ : lower bound
• big-$$ : tight bound

lecture

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