Mingchen's Blog

时间复杂度

• 递归树法

  总时间复杂度 = 递归树所有结点代价之和。常用分析方式：

  • 按层求和：各层总代价之和。如归并排序、快速排序
  • 当结点代价相同时，可用结点数 × 单结点代价。如二叉树 dfs
  • 当叶子和非叶子性质明显不同时，可分开统计。如全排列

1. 递归式法
   先写出递归式，再根据形式选择方法求解：
   • 主定理
   • 迭代展开
   • 递归树
   • 特征方程等

注意：主定理只适用于某些标准形式，如 T(n)=aT(n/b)+f(n)。

空间复杂度

递归空间复杂度主要看两部分：

1. 递归栈深度
2. 每层递归额外空间

递归栈深度通常等于递归调用树的最大路径长度（即树高）