时间复杂度和递推关系

我有困难，了解如何开发递推关系。我给出的代码是时间复杂度和递推关系

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

，但似乎并不正确。有人可以帮我吗？

来源

2017-10-20 Saff

我想你遇到麻烦在这里的原因之一是，有两个独立的参数的功能，让你的递推关系需要有两个不同的参数考虑到这一点。

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

T（m，1）= Θ（m）。

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

T（m，n）= T（m，n-1）+ O（1）。

你认为你可以从那里解决的事情？

来源

2017-10-21 00:18:34 templatetypedef

呀，这两个参数确实让我困惑，我不知道在这样的关系是否还是不写会工作。我明白你是如何得到经常性案件的，但你能否解释基本案例？我似乎无法把头围住它。另外，你将如何去获得时间复杂性？我没有做过类似的问题，所以我很抱歉，如果这对我来说应该很简单。 – Saff

在基本情况下，你只需要一个运行“第一次”的循环，每个都做O（1）。我用* m *表示你的第一个参数，所以完成的工作是O（m）。 – templatetypedef

谢谢，这清除了它。最后这给了我一些混乱的一个问题是第一行，其中为奇异的参数均为“N”，就这并不意味着第一和第二是导致基础情况为T（1,1）= O（相同的值1）？ – Saff

一般而言，复发关系由

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)

给出。在您的示例中，变量“第二”在每个递归调用越来越小1。此外，您在每个步骤中创建的子问题数量仅为一个，因为您只需调用一次该方法。

的代码并没有真正做任何工作，在除了比较各递归步骤，所以这是一个O（1）操作。

所以，

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

最后，T（1）是在基情况下，它是n个数字的总和会发生什么。

T(1) = O(n)

来源

2017-10-20 23:59:41 omijn

时间复杂度和递推关系

回答

相关问题