代码之家 › 专栏 › 技术社区 › 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)

推荐文章

Matthew Thomas · 在每个决策中给出多个选择的所有可能的决策路径/结果

1 年前

feasega · 聚合物模拟-2个节点之间的最短路线,适用于所有节点

1 年前

Alisa Petrova · 在有向图中更改一对顶点以创建循环

1 年前

Matvey Androsyuk · 如何使用React在树结构中呈现我的组件,就像IDE中的默认文件结构一样

1 年前

Pengcheng · 这个简单的递归函数的输出是什么?你能详细解释一下吗?

1 年前

b39b332d · 使用C++标准库实现高效间隔存储

1 年前

Paul C · 在维基百科上,将二叉搜索树转换为排序链表的算法是否存在错误?

1 年前

ABGR · 二叉树的直径——当最长路径不通过根时的失败案例

1 年前

SHUBHAM KUMAR · 这两个是否完全相同-->“下限(股份有限公司rbegin(),股份有限公司rend(),i,更大<int>())”和“下限(dec.begin(

1 年前

EpicAshman · 数独棋盘程序中同一列和同一行出现两次的数字

1 年前