递归的时间复杂度

简单来说，计算时间复杂度有两种：

  • 迭代法：利用数学公式迭代，算出迭代深度，并带入。
  • 递归树法: 构造出递归树，算出最大深度*当前操作的时间复杂度。

迭代法

时间复杂度的计算：

  1. T(n) = 2T(n/2) + O(n) 因为 T(n/2) = 2T(N/2) + O(n/2)
  2. .....................
  3. ---> T(n) = 2^k * T(n/(2^k)) + k*O(n)
  4. ---> n/(2^k) = 1 --> k = log2n
  5. ---> T(n) = log2n + nlog2n
  6. ---> O(nlog2n)

更多例子请看

递归树法

斐波拉契数列

递归的时间复杂度是： 递归次数*每次递归中执行基本操作的次数

所以时间复杂度是： O(2^N)

5d6f267684e7519941d3d8e0d50caa0a.JPEG