算法正确性——循环不变式
算法复杂度的计算
方法一 代换法
—局部代换
这里直接对n变量进行代换
—替换成对数或者指数的情形 n = 2^m
—整体代换
这里直接对递推项进行代换
—替换成内部递推下标的形式 T(2^n) = S(n)
方法二 递归树法
—用实例说明
—分析每一层的内容
—除了递归项的内容拿出来，如第一种树把T(n-kn)作为下一层进行计算
—递归项按层写出
方法三 主定理
—f(n)必须是n的多项式规模的才能使用主定理
—
—f(n)比较小，那么前面a,b确定的复杂度做主导
—f(n)和a,b持平，那么是2
—f(n)比较大，且满足后面的规则性条件，就以f(n)作为主导
添加次数较小的项
—由于不等式方向问题，需要抵消f(n)，需要添加不同次数的项