代码之家 › 专栏 › 技术社区 › user7493003

时间复杂度和递归关系

recurrence complexity-theory algorithm

user7493003 · 技术社区 · 8 年前

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

 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

但这似乎不对。有人能帮我吗?

2 回复 | 直到 8 年前

templatetypedef 8 年前

我认为你在这里遇到问题的原因之一是函数有两个独立的参数,所以你的递归关系需要有两个不同的参数来解释这一点。

在第二个参数为0或1的情况下,您的工作与第一个参数成比例。你可以这样写

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

否则,该函数将执行恒定量的工作,然后对相同的第一个输入和递减的第二个输入进行递归调用。这看起来是这样的:

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

你认为你能从那里解决问题吗?

omijn 8 年前

通常,递归关系由以下公式得出:

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)

除了比较之外,代码在每个递归步骤实际上都不做任何工作,因此这是一个O(1)操作。

所以

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

T(1) = O(n)

推荐文章

Roman · 有没有办法在numpy中实现无for循环的递归?

8 年前

Smeagol · Prolog中存储在列表中的重复结果

8 年前

Thunfische · 与主定理的递推关系:多项式函数

8 年前

user7493003 · 时间复杂度和递归关系

8 年前

Alviss Min · 递推方程的时间复杂度

8 年前

Nawed Khan · 如何使用Outlook REST API在重复周期中创建异常

9 年前

AdamK · 如何从算法中找到递归关系

9 年前

h3rm8 · 如何为给定的DFA在一组q状态上提出递推方程?

10 年前

DevArenaCN · 计算2个递归调用的大Theta边界

10 年前

cstac · 复杂度算法递推关系

10 年前