知识卡片

普通读书笔记卡 · 5654.c.3.h.5 · 生成模型:未记录

递推式也要有可达边界

理解等级:中级

递推式用更小规模的函数值描述当前值,也可表示递归算法的成本。归并式例T(n)=2T(n/2)+n表示两次子问题成本加本层合并成本,边界必须能覆盖递推实际到达的规模。

02685错误式把边界放在n=2,却仍让n=1继续递推;02686改为T(1)=1。正文把原边界说成n=0、把修正写作n−1均与图不一致,应按两图解释。对精确二分示意,可先限n为2的非负整数次幂;一般整数还需规定取整和不等规模分支,不能忽略定义域。

46说递推用于用子问题成本描述原问题。递推式是数学关系,不必实际运行一个递归函数才能分析;求和则可累计循环中各项成本,二者可结合使用。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 2 处

    • · 查看原书依据

      这样一种函数称为递推。在更正式的分析中,递推常用来描述递归算法的运行时间。 问:以递归的思想描述一种求解整数质因子的方法。分析该方法是否是尾递归的并解释原因。 答:递归是一种求解整数质因子的很自然的方法,因为因子分解无非就是不断地解决同样的问题。每当确定了一个因子,剩余因子的集合就变得越来越小。针对

    • · 查看原书依据

      在递归算法的分析中经常使用此方法。递推方法通常用递归函数来实现。递归函数是一个调用函数自身的函数(见第3章)。每次成功的调用都将输入的集合变得更加精细,从而越来越接近问题的答案。这种方法在描述递归算法的性能时非常有用,因为这允许我们以在更加精细的输入集合中调用这种算法来描述算法本身的性能。 求和公式

    参考来源

    - 位置:《算法精解:C语言描述》第3章《问与答》(spine1196;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1164.html;u037-ch03-006)。 - 结论依据:37第一问全文和02685-02686两公式,核对原图边界2→修正1而非正文0,解释原式n1未终止及修正的输入范围。 - 原始内容:这样一种函数称为递推。在更正式的分析中,递推常用来描述递归算法的运行时间。 问:以递归的思想描述一种求解整数质因子的方法。分析该方法是否是尾递归的并解释原因。 答:递归是一种求解整数质因子的很自然的方法,因为因子分解无非就是不断地解决同样的问题。每当确定了一个因子,剩余因子的集合就变得越来越小。针对 - 位置:《算法精解:C语言描述》第4章《相关主题》(spine1203;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1171.html;u046-ch03-006)。 - 结论依据:46说递推用于用子问题成本描述原问题。递推式是数学关系,不必实际运行一个递归函数才能分析;求和则可累计循环中各项成本,二者可结合使用。 - 原始内容:在递归算法的分析中经常使用此方法。递推方法通常用递归函数来实现。递归函数是一个调用函数自身的函数(见第3章)。每次成功的调用都将输入的集合变得更加精细,从而越来越接近问题的答案。这种方法在描述递归算法的性能时非常有用,因为这允许我们以在更加精细的输入集合中调用这种算法来描述算法本身的性能。 求和公式