时间复杂度和递归关系

Question

我很难理解如何发展递推关系。我得到的代码是

 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

但这似乎不对。有人可以帮我吗？

Answer 1

一般来说，递归关系由

给出

T(n) = no. of subproblems generated at each step * T(size of each subproblem) + complexity of the divide/conquer step

和

T(1) = complexity of base case(s)

在您的示例中，变量 "second" 在每次递归调用时变小 1。此外，您在每一步创建的子问题的数量只有一个，因为您只调用该方法一次。

除了比较之外，代码在每个递归步骤中实际上没有做任何工作，所以这是一个 O(1) 操作。

所以，

T(n) = T(n - 1) + O(1)

最后，T(1) 是基本情况下发生的情况，它是 n 个数字的总和。

T(1) = O(n)

Answer 2

我认为您在这里遇到麻烦的原因之一是该函数有两个独立的参数，因此您的递归关系需要有两个不同的参数来解决这个问题。

在您的第二个参数为 0 或 1 的情况下，您所做的工作与第一个参数成正比。你可以写成

T(m, 1) = Θ(m).

否则，该函数执行恒定量的工作，然后对相同的第一个输入和递减的第二个输入进行递归调用。这是它的样子：

T(m, n) = T(m, n - 1) + O(1).

你觉得你能从那里解决问题吗？

时间复杂度和递归关系

Time complexity and recurrence relation

algorithm

complexity-theory

recurrence