英文:
What is the Recurrence relation for the following code:
问题
代码如下：
static void fun1(int n)
{
int i = 0;
if (n > 1)
fun1(n - 1);
for (i = 0; i < n; i++)
System.out.print(" * ");
}
我的回答是：
<!-- language: none -->
T(n) = { n + 2 : 若 n <= 1
{ T(n-1) + n + 2 : 若 n > 1
基本情况包括一个赋值操作和一个比较操作（都在常数时间内），以及运行时间为线性的 for 循环。
递归情况与基本情况相同，还包括递归调用 T(n-1)。
这就是为什么我认为我是正确的，但是对于这个问题没有标准答案，所以希望能听到外部的意见。
英文:
The code is as follows:
static void fun1(int n)
{
int i = 0;
if (n > 1)
fun1(n - 1);
for (i = 0; i < n; i++)
System.out.print(" * ");
}
My answer is:
<!-- language: none -->
T(n) = { n + 2 : if n <= 1
{ T(n-1) + n + 2 : if n > 1
The base case contains one assignment and one comparison (both in constant time) as well as the for loop which runs in linear time.
The recursive case has the same as the base case as well as the recursive call T(n-1).
This is why I think I am correct but there are no answers to this problem so an external voice would be appreciated.
答案1
得分: 1
你的答案是正确的，但可以更通用地写成这样：
T(n) = T(n-1) + n + const，如果 n > 1
T(n) = n + const，如果 n <= 1
在这里，通常选择 const 的值为1，以便更容易计算，因为它对时间复杂度没有影响。
英文:
Your answer is correct, but it can written in more general way, like this :
T(n) = T(n-1) + n + const, if n > 1
T(n) = n + const, if n <= 1
And here for const you usually choose value 1, for easier calculation, beacause that doesn't have impact on time complexity.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论