写函数的递归关系

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());
}

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

Answer 1

您的第一个递归关系通常用于描述分而治之算法的运行时间.a此处显示您将数据分成多少部分,1/b显示每个部分中使用的原始数据,并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-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))

进一步阅读:

• Thomas H. Cormen 介绍算法.
• 唐纳德克努特的计算机编程艺术.