时间复杂度分析的技巧 ：

• 查找确切的和
• 写出例子
• 画图

需要记住的两个重要求和公式 ：

• 1+2+3+...+Q=Q(Q+1)/2=Θ(Q2)1+2+3+...+Q=Q(Q+1)/2=Θ(Q​2​​) （前 n 个自然数的和）
• 1+2+4+8+...+Q=2Q−1=Θ(Q)1+2+4+8+...+Q=2Q−1=Θ(Q) （前 n 个 2 的幂的和）

这个一小节还分析了二分法和归并排序的时间复杂度。

摊还分析

评价某一个操作的代价，方法就是求某数据结构一系列操作的平均时间。