基本介绍

算法（Algorithm）是指用来操作数据、解决程序问题的一组方法。对于同一个问题，使用不同的算法，也许最终得到的结果是一样的，但在过程中消耗的资源和时间却会有很大的区别。

那么我们应该如何去衡量不同算法之间的优劣呢？

主要还是从算法所占用的「时间」和「空间」两个维度去考量。

时间维度：是指执行当前算法所消耗的时间，我们通常用「时间复杂度」来描述。 空间维度：是指执行当前算法需要占用多少内存空间，我们通常用「空间复杂度」来描述。 因此，评价一个算法的效率主要是看它的时间复杂度和空间复杂度情况。然而，有的时候时间和空间却又是「鱼和熊掌」，不可兼得的，那么我们就需要从中去取一个平衡点。

下面我来分别介绍一下「时间复杂度」和「空间复杂度」的计算方式。

时间复杂度

我们想要知道一个算法的「时间复杂度」，很多人首先想到的的方法就是把这个算法程序运行一遍，那么它所消耗的时间就自然而然知道了。

这种方式可以吗？当然可以，不过它也有很多弊端。 这种方式非常容易受运行环境的影响，在性能高的机器上跑出来的结果与在性能低的机器上跑的结果相差会很大。而且对测试时使用的数据规模也有很大关系。再者，并我们在写算法的时候，还没有办法完整的去运行呢。

因此，另一种更为通用的方法就出来了：「 大O符号表示法 」，即 T(n) = O(f(n))

我们先来看个例子：

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

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

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

常见的时间复杂度量级

常见的时间复杂度量级有：

  1. 常数阶O(1)
  2. 对数阶O(logN)
  3. 线性阶O(n)
  4. 线性对数阶O(nlogN)
  5. 多项式：平方阶O(n²)，立方阶O(n³)，K次方阶O(n^k)
  6. 指数阶(2^n)

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

常数阶O(1)

无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是O(1)，如：

int i = 1;
int j = 2;
++i;
j++;
int m = i + j;

上述代码在执行的时候，它消耗的时候并不随着某个变量的增长而增长，那么无论这类代码有多长，即使有几万几十万行，都可以用O(1)来表示它的时间复杂度。

线性阶O(n)

这个在最开始的代码示例中就讲解过了，如：

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

这段代码，for循环里面的代码会执行n遍，因此它消耗的时间是随着n的变化而变化的，因此这类代码都可以用O(n)来表示它的时间复杂度。

对数阶O(logN)

还是先来看代码：

int i = 1;
while(i<n)
{
    i = i * 2;
}

从上面代码可以看到，在while循环里面，每次都将 i 乘以 2，乘完之后，i 距离 n 就越来越近了。我们试着求解一下，假设循环x次之后，i 就大于 2 了，此时这个循环就退出了，也就是说 2 的 x 次方等于 n，那么 x = log2^n 也就是说当循环 log2^n 次以后，这个代码就结束了。因此这个代码的时间复杂度为：O(logn)

线性对数阶O(nlogN)

线性对数阶O(nlogN) 其实非常容易理解，将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n * O(logN)，也就是了O(nlogN)。

就拿上面的代码加一点修改来举例：

for(m=1; m<n; m++)
{
    i = 1;
    while(i<n)
    {
        i = i * 2;
    }
}
平方阶O(n²)

平方阶O(n²) 就更容易理解了，如果把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²) 了。 举例：

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

这段代码其实就是嵌套了2层n循环，它的时间复杂度就是 O(n*n)，即 O(n²) 如果将其中一层循环的n改成m，即：

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

那它的时间复杂度就变成了 O(m*n)

立方阶O(n³)、K次方阶O(n^k)

参考上面的O(n²) 去理解就好了，O(n³)相当于三层n循环，其它的类似。

除此之外，其实还有 平均时间复杂度、均摊时间复杂度、最坏时间复杂度、最好时间复杂度 的分析方法，有点复杂，这里就不展开了。

真题练习

1、

【NOIP 2018 提高组初赛 q05】设某算法的时间复杂度函数的递推方程是T(n) = T(n - 1) + n（n 为正整数）及T(0) = 1，则该算法的时间复杂度为（ ）。
A. O(log n)   B. O(n log n)  
C. O(n)   D. O(n^2)  

2、

【NOIP 2017 提高组初赛 q06】若某算法的计算时间表示为递推关系式：
T(N) = 2T(N / 2) + N log N
T(1) = 1
则该算法的时间复杂度为（ ）。
A. O(N)O(N)   B. O(Nlog⁡N)O(N \log N)  
C. O(Nlog⁡2N)O(N \log^2 N)   D. O(N2)O(N^2)  

3、

【NOIP 2016 提高组初赛 q14】假设某算法的计算时间表示为递推关系式

T(n)=2T(N4)+sqrt(n)T(n) = 2T(\frac{N}{4})+sqrt(n)
T(1)=1T(1) = 1
则算法的时间复杂度为（ ）。
A. O(n)O(n)   B. O(n)O(\sqrt{n})  
C. O(nlog⁡n)O(\sqrt{n}\log{n})   D. O(n2)O(n^2)  

4、

【NOIP 2015 提高组初赛 q10】设某算法的计算时间表示为递推关系式 T(n) = T(n - 1) + n（n 为正整数）及 T(0) = 1，则 该算法的时间复杂度为（ ）。
A. O(log n)   B. O(n log n)  
C. O(n)   D. O(n2)  

5、

【NOIP 2013 提高组初赛 q07】斐波那契数列的定义如下：F1=1,F2=1,Fn=Fn–1+Fn–2(n≥3)F_1 = 1, F_2 = 1, F_n = F_{n – 1} + F_{n – 2} (n \ge 3)。如果用下面的函数计算斐波那契数列的第 n 项，则其时间复杂度为（ ）。

int F(int n) 
{ 
 if (n <= 2) 
  return 1; 
 else 
  return F(n - 1) + F(n - 2); 
}

A. O(1)O(1)   B. O(n)O(n)   C. O(n2)O(n^2)   D. O(Fn)O(F_n)  

6、

【NOIP 2013 提高组初赛 q15】T(n)表示某个算法输入规模为 n 时的运算次数。如果 T(1)为常数，且有递归式 T(n) = 2*T(n / 2) + 2n，那么 T(n) = （ ）。
A. Θ(n)Θ(n)   B. Θ(nlog⁡n)Θ(n \log n)  
C. Θ(n2)Θ(n^2)   D. Θ(n2log⁡n)Θ(n^2 \log n)  

7、

【NOIP 2013 提高组初赛 q17】（ ）的平均时间复杂度为 O(n log n)，其中 n 是待排序的元素个数。
A. 快速排序   B. 插入排序   C. 冒泡排序   D. 归并排序  

8、

【NOIP 2012 提高组初赛 q11】如果对于所有规模为n的输入，一个算法均恰好进行（ ）次运算，我们可以说该算法的时间复杂度为O(2n)O(2^n)。
A. 2n+12^{n+1}   B. 3n3^n  
C. n∗2nn*2^n   D. 22n2^{2n}  

9、

【NOIP 2011 提高组初赛 q07】应用快速排序的分治思想，可以实现一个求第K大数的程序。假定不考虑极端的最坏情况，理论上可以实现的最低的算法时间复杂度为（ ）。
A. O (n2)   B. O (n log n )  
C. O (n)   D. O (1)  

10、

【CSP 2019 提高组第一轮 q16】阅读程序(程序输入不超过数组或字符串定义的范围)

#include <cstdio>
using namespace std;
int n;
int a[100];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    int ans = 1;
    for (int i = 1; i <= n; ++i) {
        if (i > 1 && a[i] < a[i - 1])
            ans = i;
        while (ans < n && a[i] >= a[ans + 1])
            ++ans;
        printf("%d\n", ans);
    }
    return 0;
}

1）（1分）第16行输出ans时，ans的值一定大于i。（）
A. 正确   B. 错误  

2）（1分）程序输出的ans小于等于n。（）
A. 正确   B. 错误  

3）若将第12行的 < 改为 !=，程序输出的结果不会改变。（）
A. 正确   B. 错误  

4）当程序执行到第16行时，若ans - i> 2,则a[i + 1] ≤ a[i]。 （）
A. 正确   B. 错误  

5）(3分)若输入的a数组是一个严格单调递增的数列, 此程序的时间复杂度（）
A. O(logn)   B. O(n^2)  
C. O(nlogn)   D. O(n)  

6）最坏情况下，此程序的时间复杂度是()。
A. O(n^2)   B. O(logn)   C. O(n)   D. O(nlogn)  

11、

【CSP 2020 提高组第一轮 q17】阅读程序

#include <iostream>
#include <cstdlib>
using namespace std;

int n;
int d[10000];

int find(int L, int R, int k) {
    int x = rand() % (R - L + 1) + L;
    swap(d[L], d[x]);
    int a = L + 1, b = R;
    while (a < b) {
        while (a < b && d[a] < d[L])
            ++a;
        while (a < b && d[b] >= d[L])
            --b;
        swap(d[a], d[b]);
    }
    if (d[a] < d[L])
        ++a;
    if (a - L == k)
        return d[L];
    if (a - L < k)
        return find(a, R, k - (a - L));
    return find(L + 1, a - 13, k);
}

int main() {
    int k;
    cin >> n;
    cin >> k;
    for (int i = 0; i < n; ++i)
        cin >> d[i];
    cout << find(0, n - 1, k);
    return 0;
}

假设输入的 n， k 和 d[i] 都是不超过 10000 的正整数，且 k 不超过 n，并假设 rand() 函数产生的是均匀的随机数，完成下面的判断题和单选题：

·判断题

1）第 9 行的“x”的数值范围是 L+1 到 R，即 [L+l,R]。（ ）
A. 正确   B. 错误  

2）将第 19 行的“d[a]”改为“d[b]”，程序不会发生运行错误。（ ）

·单选题
A. 正确   B. 错误  

3）(2.5分)当输入的 d[i] 是严格单调递增序列时，第 17 行的“swap”平均执行次数是( )。
A. O(nlog⁡n)O(n \log n)   B. O(n)O(n)  
C. O(log⁡n)O(\log n)   D. O(n2)O(n^2)  

4）(2.5分)当输入的 d[i] 是严格单调递减序列时，第 17 行的“swap”平均执行次数是( )。
A. O(n2)O(n^2)   B. O(n)O(n)  
C. O(nlog⁡n)O(n \log n)   D. O(log⁡n)O(\log n)  

5）(2.5分)若输入的 d[i] 为 i，此程序①平均的时间复杂度和②最坏情况下的时间复杂度分别是( )。
A. O(n)，O(n2)O(n)， O(n^2)   B. O(n)，O(nlog⁡n)O(n)， O(n \log n)  
C. O(nlog⁡n)，O(n2)O(n \log n)， O(n^2)   D. O(nlog⁡n)，O(nlogn)O(n \log n)， O(n log n)  

6）(2.5分)若输入的 d[i] 都为同一个数，此程序平均的时间复杂度是( )。
A. O(n)O(n)   B. O(log⁡n)O(\log n)  
C. O(nlog⁡n)O(n \log n)   D. O(n2)O(n^2)