算法效率中的基本概念

2024备考建议

算法复杂度是一个必考的知识点，常常出现在阅读程序题中，让考生进行判断。

1.先理解算法模板的复杂度计算

2.再尝试套用初赛题目中的复杂度计算

3.递归算法的复杂度可以展开计算

算法效率是评估算法性能的一个关键指标，一般而言分析算法效率的方式有两种:

1. 时间复杂度
2. 空间复杂度

在一般的算法分析中，考察的主要是时间复杂度。

基本操作数

算法的运行速度受计算机性能的影响，所以通常考虑算法效率的不是算法运行的实际用时，而是算法运行所需要进行的基本操作的数量。

像加减乘除、访问变量、给变量赋值等都可以看作基本操作。对基本操作的计数或是估测可以作为评判算法用时的指标。

时间复杂度

在算法竞赛中，我们衡量一个算法的效率时，最重要的不是看它在某个数据规模下的用时，而是看它的用时随数据规模而增长的趋势，即时间复杂度。

时间复杂度是指算法运行时间与问题规模之间的关系，通常用大$O$表示法来表示。

常见的时间复杂度有：$O(1)$，$O(log n)$，$O(n)$，$O(n log n)$，$O(n^2)$，$O(2^n)$等，其中$O(1)$表示算法的运行时间不随问题规模变化而改变，而$O(2^n)$则表示算法的运行时间随问题规模 n 呈指数级增长。

变化趋势意味着我们不用纠结于具体的操作次数和 n 之间的精确对应关系，也就是不用看具体的函数的参数是什么，而只用看随着数据范围的增大，操作次数的变化是属于哪一类函数。

例如：是常数，还是线性的，还是对数的，还是$nlog n$的，还是$n2$的，还是$2n$的，还是阶乘$n!$的。原因是当 n 变得非常大的时候，这些不同类型的函数之间的差异值才是明显的，而同一种类型之间的参数不同带来的差异就显得微不足道了，可以忽略不计。这也是为什么$O(1)$和$O(3)$都被称作$O(1)$。

我们再来看个例子：

for (int i = 1; i <= n; i++) {
   j = i;
   j++;
}

这段代码的时间复杂度$O(n)$的。分析代码的执行次数，第 1 行中 i=1 执行 1 次，i<=n 和 i++ 分别执行 n 次，第 2 行、第 3 行分别执行 n 次，所以这段代码总共执行 4n+1 次。从这个结果可以看出，这个算法的耗时是随着 n 的变化而变化。如果 n 无限大的时候，1+4n 中的常量 1 就没有意义了，倍数 4 的意义也不大。因此时间复杂度直接简化为$O(n)$。

时间复杂度比较

$O(n)$、$O(logn)$、$O(n​)$、$O(nlogn)$随着 n 的增加，复杂度提升不大，因此这些复杂度属于效率高的算法，反观$O(2n)$和$O(n!)$当 n 增加到 50 时，复杂度就突破十位数了，这种效率极差的复杂度最好不要出现在程序中。（tips：通常计算机每秒可以计算的次数大约是 10 的 8 次方）

最坏、最好、平均

在进行时间复杂度分析时，需要考虑算法的最好、最坏、平均情况时间复杂度。

最好情况时间复杂度是指算法在最优输入情况下的运行时间复杂度，即在所有可能的输入情况中，算法所需的最少时间。例如，对于二分查找算法来说，在目标元素为中间元素的情况下，查找时间为$O(1)$。

最坏情况时间复杂度是指算法在最劣输入情况下的运行时间复杂度，即在所有可能的输入情况中，算法所需的最长时间。例如，对于冒泡排序算法来说，最坏情况是需要$O(n^2)$的时间复杂度。

平均情况时间复杂度是指算法在所有可能输入情况下的平均运行时间复杂度。对于某些算法来说，平均情况时间复杂度更能反映算法的运行效率，例如快速排序算法的平均情况时间复杂度为$O(nlogn)$，而最坏时间复杂度是$O(n2)$。

我们通常所说的时间复杂度大$O$是指算法的最坏时间复杂度。这是因为最坏时间复杂度能够给出算法的最长运行时间，可以帮助我们评估算法的性能并预估程序的执行时间。此外，最坏时间复杂度也是一种更保守的衡量指标，即使算法在最坏情况下表现较好，也能够保证算法的性能不会低于最坏时间复杂度。

空间复杂度

空间复杂度是指算法所需内存空间与问题规模之间的关系，是对一个算法在运行过程中临时占用存储空间大小的量度。它表示了算法在执行过程中所需的额外内存。

例如递归实现斐波那契数列，空间复杂度是$O(n)$。虽然每次调用产生两个新的递归调用fib(n - 1) + fib(n - 2)，但这些调用是顺序执行的，因此实际上只需要为最深的调用序列分配空间。最深的调用序列大约有 n 个调用，所以空间复杂度为$O(n)$。