以下代码的循环关系是什么：

ygya80vv 于 2021-07-05 发布在 Java

关注(0)|答案(1)|浏览(414)

代码如下：

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）相同。
这就是为什么我认为我是正确的，但没有这个问题的答案，所以一个外部的声音将不胜感激。

1条答案

你的答案是正确的，但可以用更一般的方式来写，比如：

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

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