Complexity of Algorithms

#Math213

Algorithm

Basic

Definition

Comparison

Time Complexity: number of machine operations
Space Complexity: amount of memory needed

Instance: 即问题对应的具体输入

Growth of Functions

Big-O Notation

注意: big-O 只要求量级大于等于即可，意味着只要找到下界，比下界大的函数都可以

注意 $\log (n!)$ 的量级
证明：

$\begin{aligned} On the one hand, & \log (n!) = \sum_{k = 1}^{n} \log (k) \leq n \log (n) & On the other hand, & \log (n!) = \sum_{k = 1}^{n} \log (k) \geq \log (\frac{n}{2} + 1) + \dots + \log (n) \geq (\frac{n}{2}) \log (\frac{n}{2}) \end{aligned}$