在NOC大赛的备考过程中，算法时间复杂度分析是非常重要的一部分，尤其是建立递归/迭代算法的复杂度计算模型以避免冗余计算这一考点。
一、递归算法复杂度计算模型
1. 知识点内容
- 递归算法的基本概念：递归算法就是在函数的定义中使用函数自身的方法。例如计算斐波那契数列，F(n)=F(n - 1)+F(n - 2)（n>=2），F(0)=0,F(1)=1。
- 复杂度分析的关键：递归算法的时间复杂度往往与递归的深度和每一层递归的操作数有关。对于像斐波那契数列这样的简单递归，其时间复杂度是指数级的，因为存在大量的重复计算。比如在计算F(5)时，F(3)会被计算两次，F(2)会被计算三次等。
- 主定理的应用：对于形如T(n)=aT(n/b)+f(n)的递归式（a>=1,b>1,f(n)是一个给定的函数），可以使用主定理来确定其时间复杂度。如果logb(a)>f(n)，则T(n)=O(nlogb(a))；如果logb(a)=f(n)，则T(n)=O(nlogb(a)logn)；如果logb(a)<f(n)，则T(n)=O(f(n))。
2. 学习方法
- 理解递归过程：通过手动计算一些简单的递归例子，如阶乘的递归实现n!=n*(n - 1)!，深入理解递归的调用过程和每一步的计算。
- 绘制递归树：对于较复杂的递归式，绘制递归树是一种很好的分析方法。以二分查找的递归实现为例，通过画出每次递归调用的范围缩小情况，直观地看到递归的深度和每层的工作量。
- 多做练习题：在网上搜索一些经典的递归算法复杂度分析题目，如归并排序、快速排序等的递归版本，反复练习使用主定理等方法来求解。
二、迭代算法复杂度计算模型
1. 知识点内容
- 迭代算法的特点：迭代算法是通过循环结构来重复执行一段代码。例如，计算1到n的累加和可以使用for循环，时间复杂度为O(n)。
- 循环嵌套的影响：如果是多层循环嵌套，时间复杂度是各层循环次数的乘积。比如一个二维数组的遍历，外层循环n次，内层循环m次，那么时间复杂度就是O(n*m)。
- 常见的迭代算法复杂度：像插入排序、冒泡排序等简单排序算法都是迭代算法，它们的时间复杂度在最坏情况下分别为O(n^2)。
2. 学习方法
- 分析循环结构：仔细研究每个循环的起始条件、终止条件和每次循环的操作数。对于有条件的循环，要考虑最好、最坏和平均情况。
- 与实际例子结合：以矩阵乘法为例，通过分析其迭代实现中的三重循环，更好地理解多层循环对时间复杂度的影响。
- 对比不同算法：将迭代算法与递归算法对比，比如比较快速排序的递归版本和迭代版本的时间复杂度，加深对迭代算法复杂度模型的理解。
三、避免冗余计算
1. 知识点内容
- 冗余计算的表现：在递归算法中，如前面提到的斐波那契数列计算，大量的重复子问题计算就是冗余计算。在迭代算法中，可能存在不必要的重复判断等情况。
- 解决方法：
- 对于递归算法，可以采用记忆化搜索的方法。例如创建一个数组来存储已经计算过的斐波那契数列的值，在每次计算前先查看数组中是否已经有结果，如果有则直接使用，避免重复计算。
- 在迭代算法中，优化循环条件和操作顺序，减少不必要的重复操作。
2. 学习方法
- 案例分析：研究一些存在冗余计算的经典案例，分析如何改进。如汉诺塔问题的非最优解法中存在很多冗余移动，对比最优解法中是如何避免的。
- 实践改进：自己动手修改一些存在冗余计算的代码，从简单的小例子开始，逐步提高能力。
总之，在考前4周的冲刺阶段，要深入理解递归/迭代算法的复杂度计算模型，多做练习，并且掌握避免冗余计算的方法，这样才能在NOC大赛中更好地应对这一考点。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
