一、算法的定义及特征

算法就是解决问题的操作步骤。一个算法必须满足以下五个重要的特征：

1. 有穷性：执行有穷步，在有穷的时间内完成。
2. 确切性：每一条指令必须有确切的含义，不会产生歧义。在任何条件下算法只有唯一的一条执行路径。
3. 可行性：算法中的操作可以通过执行有限次来实现。
4. 输入：一个算法有零个或者多个输入。
5. 输出：一个算法中有一个或者多个输出。

二、算法的复杂度

同一个问题可用不同算法来解决，而一个算法质量的优劣将影响到算法乃至程序的效率。在程序设计过程中，我们更希望程序占用更少的空间并且运行速度越快越好。所以我们通常从空间和时间上来分析算法性能。一个算法的评价主要从时间复杂度和空间复杂度来考虑。

1. 空间复杂度

空间复杂度指执行算法所需占用的内存空间。算法执行时所需的存储空间包括程序本身占用的空间、输入数据占用的空间以及算法执行时所需的空间。

算法在时间的高效性和空间的高效性之间通常是矛盾的，所以一般会取一个平衡点，通常假设程序运行在足够大的内存空间中，所以研究更多的是算法的时间复杂度。

2. 时间复杂度

在程序中，在数据规模为n时，用算法执行次数$f(n)$来衡量算法复杂度$T(n)$，影响执行次数的主要是规模n，看如下例子：

2.1 情景1

小菜同学特别爱打篮球，他每周都要打篮球两次，那他两年半（130周）会总共打篮球多少次？

显然是(2 * 130 = 260)次。

那么当时间为n周时，次数则应为$2n$次。可以看到打篮球次数$f(n)$与周数(n)存在线性关系。用函数表示：

我们所熟悉的for循环就是线性的：

在我们计算时间复杂度时，我们主要关心的是时间与问题规模的变化趋势，所以对于线性关系，我们记作$O(n)$，对于n前的系数全部设为1即可。

2.2 情景2

小菜同学决定要练习唱歌，他决定从这周开始练习1次，为了成为最强练习生，之后每周都增加练习1次，也就是第2周练习2次，第3周练习3次，第n周练习n次。可以用如下代码来表示：

2.3 计算规则：

(1) 加法规则：$T(n,m) = T1(n) + T2(m) = O(max\{f(n),g(m)\})$ //并列算法

(2) 乘法规则：$T(n,m) = T1(n) * T2(m) = O(f(n)*g(m))$ //嵌套算法

2.4 时间复杂度按n增长速度排序：

$O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(n^3) < ... < O(n^k) < O(n!)$。

• $O(1)$: 常数时间复杂度
• $O(\log n)$: 对数时间复杂度
• $O(n)$：线性时间复杂度
• $O(n^2)$：平方时间复杂度
• $O(n^3)$：立方时间复杂度
• $O(n^k)$：指数时间复杂度，k表示常数
• $O(n!)$：阶乘时间复杂度

2.5 递推算法时间复杂度计算

根据递推关系式一路推导得出结果。

习题：

1. 【NOIP2016】 假设某算法的计算时间表示为递推关系式

则算法的时间复杂度为（ ）。 {{ select(1) }}

• O(n)
• O(√n)
• O(√nlogn)
• O(n^2)

2. 计算时间复杂度1

$f(n) = 2n^3 + 10000n$

T(n) = O(n^{{ input(2) }})

3. 计算时间复杂度2

$f(n) = n\log n + n$

$T(n) =$O({{ input(3) }})

4. CSPJ2021 入门组 17 题：分析代码的时间复杂度O({{ input(4) }})

5. NOIP2013 斐波那契数列的定义如下：

斐波那契数列的定义如下：F1 = 1, F2 = 1, Fn = Fn−1 + Fn−2(n ≥ 3)。如果用下面的函数计算斐波那契数列的第n项，则其时间复杂度为（ ）。

{{ select(5) }}

• $O(1)$
• $O(n)$
• $O(n^2)$
• $O(F_n)$

6. 模拟题 分析下列代码时间复杂度。

O(n*{{ input(6) }})

7. 模拟题 分析下列代码时间复杂度。

---

O({{ input(7) }})

8. 模拟题 假设某算法的计算时间表示为递推关系式 T(n) = 8T(n/2) + n^2 T(1) = 1

则算法的时间复杂度为（ ）。 {{ select(8) }}

• O(n)
• O(√n)
• O(n^2)
• O(n^3)

9. 模拟题 假设某算法的计算时间表示为递推关系式

T(n) = 8T(n/2) + n^4 T(1) = 1

则算法的时间复杂度为（ ）。 {{ select(9) }}

• O(n)
• O(n^2)
• O(n^3)
• O(n^4)

10. 模拟题 假设某算法的计算时间表示为递推关系式

T(n) = 8T(n/2) + n^3 T(1) = 1

则算法的时间复杂度为（ ）。 {{ select(10) }}

• O(n)
• O(n^3)
• O(n^3 log n)
• O(n^4)