1

我知道递归关系的公式是 T(n)=aT(n/b)+f(n)。鉴于这个方程，我知道如何求解 BigO。我的作业问题要求我编写一个递归函数来计算列表中的节点数，我这样做了，但后来要求我编写一个递归关系。这是我的代码：

int count(ListNode *l)
{
    if(!l) return 0;
    if(!l->next) return 1;

    return 1 + count(l->getNext());
}

但是我完全不知道如何创建/制定我自己的递归关系公式......我如何找到a或b......我不知道从哪里开始。如何编写此函数的递归关系？谢谢你。

4

2 回答 2

5

您的第一个递归关系通常用于描述分治算法的运行时间。a这里显示您将数据划分为多少部分，显示1/b每个部分中使用了哪些原始数据，并f(n)显示每个“级别”需要多少时间。例如，在 QuickSort 算法中，您将数据（数组或列表）分成 2 部分，每部分恰好是原始数据的一半（1/2），并且在划分的每个“级别”上，您需要遍历所有n元素 1时间。所以递归关系是

T(n) = 2T(n/2) + n

（计算结果为 O(n * lg(n))）在二分搜索中，您将数据分为 2 部分，但只取其中 1 部分，并且每个“级别”上的时间是恒定的，因此关系是：

T(n) = T(n/2) + 1

但是，您在 C 中的函数不遵循分而治之的策略。相反，它演示了数学归纳法。您定义开始条件：如果l等于NULL，则长度为 0，如果l->next等于NULL（您还为列表中的 1 个元素定义条件）。然后定义一种归纳步骤 - 如果您知道第 (n - 1) 个元素的函数值，则定义如何计算第 n 个元素的函数。因此，知道第一个元素的函数值，您可以应用此规则并获取第二个元素的值，然后获取第三个元素的值，依此类推。

所以你可以看到归纳法本质上是递归算法。这里我们有 2 次需要考虑。首先是在起点（或终点 - 这取决于您查看列表的顺序）计算值的时间。在您的函数中，您只需返回此值，因此它是常量 ( C1)。其次是迈出第一步的时间。在您的函数中，它也是常数 ( C2)。直观地你应该看到这个算法的执行时间将是：

T(n) = C1, when n = 1 
T(n) = T(n - 1) + C2, when n > 1

因此，除非n = 1，您定义在元素上执行算法的n时间到在元素上执行算法的时间n - 1。在 BigO 表示法中，任何常数都定义为1，并且不考虑 1 个元素的情况，因此您的最终递归关系为：

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

（计算结果为T(n) = T(n - 1) + 1 = T(n - 2) + 2 = ... = 1 + n, 或O(n)）

进一步阅读：

于 2012-03-05T01:06:19.687 回答
2

我很久没有写递归关系了，但这应该是答案：T(n) = T(n-1) + CONSTANT。你的公式是：T(n)=aT(n/b)+f(n)。b : 你把问题分成 b 部分。f(n) ：是用多少时间来解决问题 a：问题的实例数 在您的问题中您将问题线性减少 1。所以它是 n-1。常数意味着解决问题需要一些常数时间

PS：我8年没用过递归关系，但就是这样。

于 2012-03-04T23:32:38.197 回答