CS 240复习总结之一: Asymptotic Analysis
Author: 咳嗽di小鱼 Date: April 5, 2011 Category: Sum Up No Comments
Runtime的符号
- Big-O 表示当c和n0在达到一定大小以后, runtime小于等于某一数级[g(x)]
- Little-O (与Big-O对应) 表示当c和n0为任意值时, runtime一定小于某一数级[g(x)]
- Ω 表示当c和n0达到一定大小以后, runtime大于等于某一数级[g(x)]
- ω (与Ω对应) 表示c和n0为任意值时, runtime一定大于某一数级[g(x)]
- Θ 为同时满足Big-O和Ω
常见的Runtime数级
- Logarithmic (log n)
- Linear (n)
- Linearithmic (n log n)
- Quadratic (n^2)
- Cubic (n^3)
- Exponential (2^n)
更多CS 240总结请看: http://blog.gregwym.info/tag/cs240/