算法时间复杂度

cf(N)上界
cg(N)下界

大O表示法 包含 小o表示法、θ表示法
重合曲线也算上界曲线

小于等于去掉等于的情况

在实际应用中 用大O表示法 找最小的那个上界

在考研中 看到的是大O表示法 实际上用的是θ表示法 比较容易找到 h（N）

最好、最坏、与平均情况

考研中 题目不做特殊要求 让你求某个算法的时间复杂度
都是求最坏情况的时间复杂度

普通函数的时间复杂度计算方法

递归函数的时间复杂度计算方法
推导求解法

随着k的变大 n/2^k 会越来越小 会小于等于1的时候
取n/2^k 等于1时 代表low等于high
递归函数跳出
于是取n = 2^k 这个点作为结束的点

当n=1时 数据规模为1 ，low= high
可以认为是常量级运算
T（1） = c；

公式求解法

换底公式

时间复杂度没有写底数时
代表底数可以任意取

如图中所证
不管log是以几为底的n
底数只能影响表达式的系数
而不能影响次数
对时间复杂度没有影响
所以有的干脆不写底数了
当然考试写出来也没错