我很难理解如何发展递归关系。我给出的代码是
int result = bizarre(n, n);
public static int bizarre (int first, int second)
{
if (second <= 1)
{
int temp = 0;
for (int i = 0; i < first; i++)
temp += i;
return temp;
}
return bizarre (first, second-1);
}
据我了解
T(n) = n + 1
T(1) = 1
但这似乎不对。有人可以帮帮我吗？
最佳答案
我认为您在这里遇到麻烦的原因之一是该函数有两个独立的参数，因此您的递归关系需要有两个不同的参数来解决这个问题。
如果您的第二个参数是 0 或 1，您所做的工作与第一个参数成正比。你可以这样写
T(m, 1) = Θ(m).
否则，该函数会执行恒定量的工作，然后对相同的第一个输入和递减的第二个输入进行递归调用。这是它的样子:
T(m, n) = T(m, n - 1) + O(1).
你认为你可以从那里解决问题吗？
关于algorithm - 时间复杂度和递推关系，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/46858401/