算法分析指对一个算法所需要的资源进行预测：内存、通信带宽、计算机硬件、希望测度的计算时间

希望找到输入规模与所需资源的关系

严格地说,输入规模指用二进制表示输入所需的总位数;例如，一个数组有n个元素，每个元素用b位二进制数表示，其输入规模为n*b

往往忽略位数，但是大数相加或者相乘运算不可以忽略

• 指令一条一条执行，没有并行
• 包含了所有常见指令：加减乘除和位运算等
• 所有的指令运行时间都为常数
• 数据类型分为整数类型和浮点实数类型

算法最坏情况运行时间T(n),因为T(n)一般仅定义于整数的输入规模上

一个渐进正函数中的低阶项在决定渐进确界时可以被忽略，高阶项的系数也可以忽略

Θ O Ω o ω五种记号

O记号是用来表示上界的，当用它作为算法的最坏情况运行时间的上界，就对任意输入有运行时间的上界

• 渐进确界 Θ 类似于两条曲线夹逼和函数极限定义 非严格不等式
• 渐进上界 O 非紧确的 如an+b = O(n^2) 非严格不等式
• 渐进下界 Ω 非紧确的 如3n^3 = Ω(n^2) 非严格不等式
• 紧确渐进上界 o 例如2n = o(n^2) 2n^2 != o(n^2) 严格等式
• 紧确渐进上界 ω 例如2n^2 = ω(n) 2n^2 != ω(n^2) 严格等式

f(n) = O(g(n)) ≈ a ≤ b f(n) = Ω(g(n)) ≈ a ≥ b f(n) = Θ(g(n)) ≈ a = b f(n) = o(g(n)) ≈ a < b f(n) = ω(g(n)) ≈ a > b

• 0.5n^2 - 3n = Θ(n^2)
• 2n^2 + 3n + 1 = 2n^2 + Θ(n)
• 2n^2 + Θ(n) = Θ(n^2)

• 传递性：5个渐进记号均满足
• 自反性：
• 对称性：Θ
• 转置对称性：f(n) = O(g(n)) 当且仅当 g(n) = Ω(f(n)), f(n) = o(g(n)) 当且仅当 g(n) = ω(f(n))

• 因此任意正多项式函数都比多项对数函数增长的快
• f(n) = O(lgn^k) 对数有界
• lim n^b / a^n = 0 lgn^b = o(n^a)

• n! = o(n^n) = ω(2^n)
• lg(n!) = Θ(nlgn)
• 多重对数函数 lg * n; lg * 2 = 1; lg * 4 = 2; lg * 16 = 3; lg * 65535 = 5;
• 斐波那契函数 Fi = Fi-1 + Fi-2 = (phi^i - phi*^i) / sqrt(5) phi = (1 + sqrt(5)) / 2; phi* = (1 - sqrt(5)) / 2; 斐波那契数以指数形式增长