算法设计与分析基础 | 时间复杂度分析

算法运行时间计算公式

对于大规模的数，效率分析时时常忽略乘法常量，仅关注执行次数的增长次数及其常数倍

符号 O,

是增长次数小于等于 g(n) 的函数集合。比如 g(n) = ，即 。那么就有

定义：当 时， ，其中 c 是大于 0 的常数

---

是增长次数大于等于 g(n) 的函数集合。比如 g(n) = ，即 。那么就有

定义：当 时， ，其中 c 是大于 0 的常数

---

是增长次数等于 g(n) 的函数集合。比如 g(n) = ，即 。那么就有

如何简单判断 t(n) 属于

利用极限比较增长次数

递归算法效率分析

反向替换法

齐次二阶线性递推式：斐波那切数列

该算法基本操作是加法，把 A(n) 定义为在计算 F(n) 过程中所做的加法次数，那么就有：

分析斐波那切数列的效率

总结

利用极限判断

递归算法的效率分析方法：

1. 反向替换法
2. 齐次二阶线性递推式