java - 以下代码的递归关系是什么：

Question

代码如下：

static void fun1(int n)  
{  
   int i = 0;    
   if (n > 1)  
     fun1(n - 1);  
   for (i = 0; i < n; i++)  
     System.out.print(" * ");  
}

我的回答是：

T(n) = { n + 2          : if n <= 1
       { T(n-1) + n + 2 : if n > 1

基本情况包含一项分配和一项比较（均在恒定时间内）以及以线性时间运行的 for 循环。

递归情况与基本情况以及递归调用 T(n-1) 相同。

这就是为什么我认为我是正确的，但这个问题没有答案，所以外部的声音将不胜感激。

标签： javarecursiontimetime-complexityrecurrence

Answer 1

你的答案是正确的，但它可以写成更一般的方式，像这样：

T(n) = T(n-1) + n + const, if n > 1
T(n) = n + const, if n <= 1

在这里const 你通常选择值1，以便于计算，因为它对时间复杂度没有影响。