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

时间复杂度和递归关系

recurrence complexity-theory algorithm

user7493003 · 技术社区 · 7 年前

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

 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 回复 | 直到 7 年前

templatetypedef 7 年前

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

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

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

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

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

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

omijn 7 年前

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

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)

推荐文章

Suhail Gupta · 在排序阵列中查找目标范围的时间复杂度-此解在最坏情况下是否为O(N)?

2 年前

Liana78 · 查找和最小化合并排序算法运行时分析

6 年前

Lamaman · 素数算法的复杂度是多少?

6 年前

irish Senthil · 声明变量是否对大O表示法有效?

6 年前

shir k · 大阵列中1的θ

6 年前

Monk · 为什么大Oh不总是算法的最坏情况分析?

6 年前

Faisal Alzahrani · 用Java计算程序的Big-O

6 年前

Dazcii · 如何找到3个嵌套循环的复杂性

6 年前

svaerth · 使用巨型哈希表在多项式时间内求解数独

6 年前

shinwari_afg · 使用大Oh分析while(key<=N*N)循环的复杂性

6 年前