什么是算法？

算法：就是解决问题的程序化方案或计算步骤。

学习算法目的：采用不同的算法策略，设计高效率的程序。

程序 = 算法 + 数据结构 （由图灵奖获得者 Niklaus Wirth 提出）。

例如，编程要求从 1 + 2 + 3 + ... + n，如果用循环，就要执行 n 次累加操作，如果用等差数列求和公式，可以直接得到结果：(a1+an)n/2。

算法竞赛或者在测评网站刷题时，都会有一个时间限制和空间限制（内存限制），时间限制一般为 1s，对于 C++ 来说，大概可以执行 1亿 次。如果外层循环枚举 10000 次，内层循环也枚举 10000 次，那么基本就会超时。

我们主要考虑程序运行时间，空间一般不会超出程序最大限制。如上图所示，空间为 256 MB，计算可以存储多少个 int 类型数据？

256 * 1024 * 1024 / 4 = 67108864，大概 6千万 多些。

算法的特征

1. 有穷性：算法的每个操作步骤都能在有限的时间内完成。

2. 确定性：每一步都必须有明确的定义，不允许有歧义性和多义性。

3. 输入：一个算法应该有0个或多个输入；

4. 输出：有一个或多个输出；

5. 可行性：每一个操作都应该是特定的解题规则中允许使用的、可执行的，并可以通过执行有限次来实现。

算法的评定

同一个问题，可用不同的算法来解决，而一个算法质量的优劣将影响程序的效率。 一个算法的评价主要从时间复杂度和空间复杂度来考虑。例如，计算 1 ~ n 之间整数和问题。

1. 时间复杂度 ：指执行算法所需要的计算工作量。

2. 空间复杂度 ：算法需要消耗的内存空间。

3. 算法正确性 ：评价一个算法优劣的最重要的标准。

4. 算法可读性 ：算法可供人们阅读的容易程度。

5. 算法鲁棒性 ：算法对不合理数据输入的反应能力和处理能力，也称为容错性。

如何计算程序执行时间？

最简单的思路，就是在程序开始时记录一下时间，结束时再记录一下时间，然后计算时间差。

#include <iostream>
#include <cstdio>
#include <sys/time.h>
using namespace std;

int main() {

    struct timeval start, end;
    gettimeofday(&start, NULL);
    
    int cnt = 0;
    for(int i = 1; i <= 1000000000; i++)
        cnt++;
    
    gettimeofday(&end, NULL);

    int t = 1000000 * (end.tv_sec - start.tv_sec) + end.tv_usec - start.tv_usec;
	t = t * 1.0 / 1000;
    
    printf("该程序用时%dms\n", t);

	return 0;
}

这种方式非常容易受运行环境的影响，在性能高的机器上跑出来的结果与在性能低的机器上跑的结果相差会很大。而且对测试时使用的数据规模也有很大关系。

我在 Windows 系统中 Dev C++ 运行得到如下结果：

在虚拟机中 NOI Linuux 运行得到如下结果：

如果机器性能差距很大，这种测评机制是不公平的。

那么，如何选择一种有效方案可以抛开机器性能差距，对不同算法效率进行评价呢？

大O表示法

通过大O符号表示法，这段代码的时间复杂度为 O(n) ，为什么呢？

int main() {
	
    int n;
    cin >> n;
    
    for(int i = 1; i <= n; i++)
        cout << i << " ";

	return 0;
}

在大O符号表示法中，时间复杂度的公式是： T(n)=O(f(n))

注：f(n) 表示每行代码执行次数之和，而 O 表示正比例关系，这个公式的全称是：算法的渐进时间复杂度。

算法复杂度可以从最理想情况、平均情况和最坏情况三个角度来评估，由于平均情况大多和最坏情况持平，而且评估最坏情况也可以避免后顾之忧，因此一般情况下，我们设计算法时都要直接估算最坏情况的复杂度。

大O表示法具体如何表示呢？

比如某个算法的时间复杂度如下，其中n代表数据量。

推导大O阶，我们可以按照如下的规则则来进行推导，得到的结果就是大O表示法：

1. 用常数1来取代运行时间中所有加法常数。

2. 修改后的运行次数函数中，只保留最高阶项

3. 如果最高阶项存在且不是1，则去除与这个项相乘的常数。

高次项对时间复杂度的影响更大，而低次项则可以被忽略，于是，我们可以将上述时间复杂度变成： 3n^3 现在，我们发现高次项前面的系数并不特别影响时间复杂度所在的数量级，于是就将系数也省去，最后时间复杂度变为： n^3，这样，我们就得到了这个算法的时间复杂度了O(n^3) 。

常见时间复杂度

常数阶 O(1)

对数阶 O(logn)

线性阶 O(n)

线性对数阶

O(nlogn)

平方阶 O(n^2)

立方阶 O(n^3)

k次方阶 O(nk)

指数阶 O(2^n)

阶乘阶 O(n!)

从上至下依次的时间复杂度越来越大，执行的效率越来越低。

答题时，可以根据数据范围大小预先估算一下时间复杂度，进而选择合适的算法：

例1：时间复杂度：O(log2n)

例2：时间复杂度：O((√n))

例3：时间复杂度为O(n)

例4：时间复杂度为O(n)

解析：这是道易错题。很多同学会认为最外层循环执行了logN次，最内层N次，所以总时间复杂度为 O(NlogN) 次。这就是经典的错误。
正解：考虑下 cnt++ 会运行多少次：当 i=n 时，它将运行 N 次。当 i=n/2 时，它将运行 n/2 次。当 i=n/4 时，它将运行 n/4 次。以此类推，cnt++ 总共会运行 n+n/2+n/4+…+1=2?n 次。因此时间复杂度为O(n) 。

空间复杂度

和时间复杂度类似，空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量，也是使用大O表示法。

1. 常量空间：存储空间大小固定，和输入没有关系时，空间复杂度是 O(1)

2. 线性空间：算法中定义了一个线性集合，如一个列表，并且集合大小和输入规模 n 成正比，空间复杂度记为O(n)

3. 二维空间：算法中定义了一个二维列表集合，并且集合的长和宽都和输入规模 n 成正比，空间复杂度记为 O(nn) 或 O(nm)

【NOIP2011】在使用高级语言编写程序时，一般提到的“空间复杂度”中的空间是指（ ）。

A. 程序运行时理论上所占的内存空间

B. 程序运行时理论上所占的数组空间

C. 程序运行时理论上所占的硬盘空间

D. 程序源文件理论上所占的硬盘空间

答案：A