algorithm - 写出函数的递推关系

Question

我知道递归关系的公式是 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...我不知道从哪里开始。这个函数的递归关系怎么写？谢谢。

Answer 1

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

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

(计算结果为 O(n * lg(n)))在二进制搜索中，您将数据分成两部分，但只取其中的一部分，并且每个“级别”上的时间是恒定的，所以关系是:

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

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

可见归纳法本质上就是递归算法。这里我们有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))

进一步阅读:

• Introduction to Algorithms托马斯·H·科门 (Thomas H. Cormen)。
• Art of Computer Programming唐纳德·高德纳 (Donald Knuth)。