首页 > 其他分享 >递归问题 的时间复杂度

递归问题 的时间复杂度

时间:2023-03-28 22:27:21浏览次数:37  
标签:调用 log 递归 复杂度 子函数 时间 常数

gong公式:

T(N) = a * T(N/b) + O(N^d)

其中(abd都是常数)

 

N:入参,输入集合

a:调用子函数的次数

b:调用子函数的规模

d:除子递归外的常数操作,没有为0,如果有N次为1 如果有N^2 次 为2 

 

推导时间复杂度公式:

  1. log b a  >d  O(N log b a)

       2. log b a  <d  O(N ^ d)

  3. log b a  =d  O(N ^ d * log N)

 

例子:

  求数组arr中的最大数,用递归实现

 

标签:调用,log,递归,复杂度,子函数,时间,常数
From: https://www.cnblogs.com/quzhongren/p/17266986.html

相关文章