算法效率

算法效率分析分为两种:第一是时间效率，第二是空间效率。时间效率被称为时间复杂度，空间效率被称为空间复杂度。

时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度主要衡量一个算法所需要的额外空间。在计算机发展的早期，计算机的存储空间很小，所以对空间复杂度很是在乎。但是随着计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以如今已经不需要再特别关注一个算法的空间复杂度。这就是为什么我们大多时候听到的是时间复杂度，而很少听到空间复杂度的原因。

什么是大O

这里的大O是指什么?说到时间复杂度，大家都知道O(n),O(n^2),却说不清什么是大O.

算法导论中说道:大O是用来表示上界的，当用它作为算法的最坏情况运行时间的上界，就是对任意数据输入的运行时间的上界。

同样算法导论中给出了例子:拿插入排序来说，插入排序的时间复杂度为O(n^2).

输入数据的形式对程序运算时间是有很大影响的，在数据本来就有序的情况下时间复杂度为O(n),但如果数据是逆序的话，插入排序的时间复杂度就是O(n^2),也就对于所有输入情况来说，最坏是O(n^2)的时间复杂度，所以称插入排序的时间复杂度为O(n^2)。

同样的同理再看一下快速排序，都知道快速排序是O(nlogn)，但是当数据已经有序情况下，快速排序的时间复杂度是O(n^2) 的，所以严格从大O的定义来讲，快速排序的时间复杂度应该O(n^2)。

但是我们依然说快速排序是O(nlogn)的时间复杂度，这个就是业内的一个默认规定，这里说的O代表的就是一般情况，而不是严格的上界。如图所示：

我们主要关心的还是一般情况下的数据形式。

面试中说道算法的时间复杂度是多少指的都是一般情况。但是如果面试官和我们深入探讨一个算法的实现以及性能的时候，就要时刻想着数据用例的不一样，时间复杂度也是不同的，这一点是一定要注意的。

时间复杂度分析

概念

时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。

先来看看下面这串代码，计算一下Func1中++count语句总共执行了多少次?

void Func1(int N)
{
  int count = 0;
  //代码1
  for (int i = 0; i < N; ++i)
  {
    for (int j = 0; j < N; ++j)
    {
      ++count;
    }
  }
  //代码2
  for (int k = 0; k < 2 * N; ++k)
  {
    ++count;
  }
  //代码3
  int M = 10;
  while (M--)
  {
    ++count;
  }
  printf("%d\n", count);
}

在代码1中++count执行了N*N次

在代码2中++count执行了N次

在代码2中++count执行了10次

所以总共执行次数为（N^2+N+10）次。

我们得到只有一个函数关系：

F(N)=N^2+N+10

当N足够大时F(N)的大小主要由N^2决定，实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，所以这里我们使用大O的渐进表示法。

什么是大O渐进表示法呢？

大O渐进表示法

大O符号:用于描述函数渐进行为的数学符号。

推导大O阶方法:

1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，只保留最高阶项。
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶

所以上面所说的F(N)=N^2+N+10函数用大O渐进表示法得到的结果是O(N ^ 2)，这样我们就舍去了影响不大的项，简单明了地表示出了执行的次数。

不同数据规模的差异

如下图中可以看出不同算法的时间复杂度在不同数据输入规模下的差异。

在决定使用哪些算法的时候，不是时间复杂越低的越好(因为简化后的时间复杂度忽略了常数项等等), 要考虑数据规模，如果数据规模很小甚至可以用O(n^2)的算法比O(n)的更合适(在有常数项的时候)。

就像上图中 O(5n^2) 和 O(100n) 在n为20之前 很明显 O(5n^2)是更优的，所花费的时间也是最少的。

那为什么在计算时间复杂度的时候要忽略常数项系数呢，也就说O(100n) 就是O(n)的时间复杂度，O(5n^2) 就是O(n^2)的时间复杂度，而且要默认O(n) 优于O(n^2) 呢 ？

这里就又涉及到大O的定义，因为大O就是数据量级突破一个点且数据量级非常大的情况下所表现出的时间复杂度，这个数据量也就是常数项系数已经不起决定性作用的数据量。

例如上图中20就是那个点，n只要大于20 常数项系数已经不起决定性作用了。

所以我们说的时间复杂度都是省略常数项系数的，是因为一般情况下都是默认数据规模足够的大，基于这样的事实，给出的算法时间复杂的的一个排行如下所示：

O(1)常数阶 < O(logn)对数阶 < O(n)线性阶 < O(n^2)平方阶 < O(n^3)立方阶 < O(2^n)指数阶

但是也要注意大常数，如果这个常数非常大，例如10^7 ，10^9 ，那么常数就是不得不考虑的因素了。

复杂表达式的化简

有时候我们去计算时间复杂度的时候发现不是一个简单的O(n) 或者O(n^2)， 而是一个复杂的表达式，例如：

O(2*n^2 + 10*n + 1000)

那这里如何描述这个算法的时间复杂度呢，一种方法就是简化法。

去掉运行时间中的加法常数项 （因为常数项并不会因为n的增大而增加计算机的操作次数）。

O(2*n^2 + 10*n)

去掉常数系数（上文中已经详细讲过为什么可以去掉常数项的原因）。

O(n^2 + n)

只保留保留最高项，去掉数量级小一级的n （因为n^2 的数据规模远大于n），最终简化为：

O(n^2)

所以最后我们说：这个算法的算法时间复杂度是O(n^2) 。

O(logn)中的log是以什么为底?

平时说这个算法的时间复杂度是logn的，那么一定是log 以2为底n的对数么？

其实不然，也可以是以10为底n的对数，也可以是以20为底n的对数，但我们统一说 logn，也就是忽略底数的描述。

为什么可以这么做呢？如下图所示：

假如有两个算法的时间复杂度，分别是log以2为底n的对数和log以10为底n的对数，那么这里如果还记得高中数学的话，应该不难理解以2为底n的对数 = 以2为底10的对数 * 以10为底n的对数。

而以2为底10的对数是一个常数，在上文已经讲述了我们计算时间复杂度是忽略常数项系数的。

抽象一下就是在时间复杂度的计算过程中，log以i为底n的对数等于log 以j为底n的对数，所以忽略了i，直接说是logn。

这样就应该不难理解为什么忽略底数了。

案例分析

案例1:

void Func1(int N)
{
  int count = 0;
  for (int k = 0; k < 2 * N; ++k)
  {
    ++count;
  }
  int M = 10;
  while (M--)
  {
    ++count;
  }
  printf("%d\n", count);
}

时间复杂度:

第一个循环执行了2*N次，第二个循环执行了10次。 总共执行了 2 * N+10次。

最高阶项是2 * N，所以时间复杂度是O(N)。

案例2

void Func2(int N, int M)
{
  int count = 0;
  for (int k = 0; k < M; ++k)
  {
    ++count;
  }
  for (int k = 0; k < N; ++k)
  {
    ++count;
  }
  printf("%d\n", count);
}

时间复杂度:

第一个循环执行了M次，第二个循环执行了N次。 总共执行了 M+N次。

最高阶项是M和N，所以时间复杂度是O(M+N)

当M>>N时，时间复杂度是O(M)

当M近似等于N时，时间复杂度是O(M+N)

当M<

案例3:

void Func3(int N)
{
  int count = 0;
  for (int k = 0; k < 100; ++k)
  {
    ++count;
  }
  printf("%d\n", count);
}

时间复杂度

这个循环执行了100次， 总共执行了100次。

最高阶项是100，执行次数为常数次，所以时间复杂度是O(1)。

案例4

// 计算strchr的时间复杂度？
const char * strchr(const char * str, int character);

strchr是一个在字符串中查找某个字符的算法，计算strchr的时间复杂度？

在一个字符串中查找一个字符，肯定要变量这个字符串，所以会利用循环，遍历长度次，由于长度是未知的，所以最高阶项N。

最好是1，最坏是N，平均是N/2，由于时间复杂度的计算看的是最坏的情况，所以时间复杂度是O(N)。

时间复杂度:

这个循环执行了100次， 总共执行了100次。

最高阶项是100，执行次数为常数次，所以时间复杂度是O(1)。

案例5

void BubbleSort(int* a, int n)
{
  assert(a);
  for (size_t end = n; end > 0; --end)
  {
    int exchange = 0;
    for (size_t i = 1; i < end; ++i)
    {
      if (a[i - 1] > a[i])
      {
        Swap(&a[i - 1], &a[i]);
        exchange = 1;
      }
    }
    if (exchange == 0)
      break;
  }
}

时间复杂度

执行次数为(n-1)+…2+1

这是一个等查数列求和，结果是n *（n-1）/2。

最高阶项是N ^ 2，所以时间复杂度是O(N ^ 2)

案例6

int BinarySearch(int* a, int n, int x)
{
  assert(a);
  int begin = 0;
  int end = n - 1;
  while (begin < end)
  {
    int mid = begin + ((end - begin) >> 1);
    if (a[mid] < x)
      begin = mid + 1;
    else if (a[mid] > x)
      end = mid;
    else
      return mid;
  }
  return -1;
}

二分查找算法的时间复杂度

N/2/2/2..../2/2=1

假设除了n次2，所以有:N/2^n=1->N=2^n

n=log2(N)

所以计算得到时间复杂度为:O(logN)

案例7

// 计算阶乘递归Fac的时间复杂度？
long long Fac(size_t N)
{
  if (0 == N)
    return 1;
  return Fac(N - 1)*N;
}

计算阶乘递归Fac的时间复杂度?

计算F(N)，利用递归调用F(N) = N*F(N-1)

F(N-1) = (N-1) * F(N-2)

F(N-2) = (N-2) * F(N-3)

…

F(2) = 2 * F(1)

F(1) = 1

这样一共递归调用了N次，所以时间复杂度是O(N)。

案例8

// 计算斐波那契递归Fib的时间复杂度？
long long Fib(size_t N)
{
  if (N < 3)
    return 1;
  return Fib(N - 1) + Fib(N - 2);
}

时间复杂度

调用次数求得:2^0+2^1...2^(n-1)=2^n-1

时间复杂度为:O(2^n)

算法为什么会超时

一些同学可能对计算机运行的速度还没有概念，就是感觉计算机运行速度应该会很快，那么在leetcode上做算法题目的时候为什么会超时呢？

计算机究竟1s可以执行多少次操作呢？ 接下来探讨一下这个问题。

大家在leetcode上练习算法的时候应该都遇到过一种错误是“超时”。

也就是说程序运行的时间超过了规定的时间，一般OJ（online judge）的超时时间就是1s，也就是用例数据输入后最多要1s内得到结果，暂时还不清楚leetcode的判题规则，下文为了方便讲解，暂定超时时间就是1s。

如果写出了一个$O(n)$的算法 ，其实可以估算出来n是多大的时候算法的执行时间就会超过1s了。

如果n的规模已经足够让$O(n)$的算法运行时间超过了1s，就应该考虑log(n)的解法了。

计算机的运算速度主要看CPU的配置，以2015年MacPro为例，CPU配置：2.7 GHz Dual-Core Intel Core i5 。

也就是 2.7 GHz 奔腾双核，i5处理器，GHz是指什么呢，1Hz = 1/s，1Hz 是CPU的一次脉冲（可以理解为一次改变状态，也叫时钟周期），称之为为赫兹，那么1GHz等于多少赫兹呢

• 1GHz（兆赫）= 1000MHz（兆赫）
• 1MHz（兆赫）= 1百万赫兹

所以 1GHz = 10亿Hz，表示CPU可以一秒脉冲10亿次（有10亿个时钟周期），这里不要简单理解一个时钟周期就是一次CPU运算。

例如1 + 2 = 3，cpu要执行四次才能完整这个操作，步骤一：把1放入寄存机，步骤二：把2放入寄存器，步骤三：做加法，步骤四：保存3。

而且计算机的cpu也不会只运行我们自己写的程序上，同时cpu也要执行计算机的各种进程任务等等，我们的程序仅仅是其中的一个进程而已。

所以我们的程序在计算机上究竟1s真正能执行多少次操作呢？

在写测试程序测1s内处理多大数量级数据的时候，有三点需要注意：

• CPU执行每条指令所需的时间实际上并不相同，例如CPU执行加法和乘法操作的耗时实际上都是不一样的。
• 现在大多计算机系统的内存管理都有缓存技术，所以频繁访问相同地址的数据和访问不相邻元素所需的时间也是不同的。
• 计算机同时运行多个程序，每个程序里还有不同的进程线程在抢占资源。

尽管有很多因素影响，但是还是可以对自己程序的运行时间有一个大体的评估的。

所以任何开发计算机程序员的软件工程师都应该能够估计这个程序的运行时间是一秒钟还是一年。

这个是最基本的，所以以上误差就不算事了。

以下以C++代码为例：

测试硬件：2015年MacPro，CPU配置：2.7 GHz Dual-Core Intel Core i5

实现三个函数，时间复杂度分别是 $O(n)$ , $O(n^2)$, $O(n\log n)$，使用加法运算来统一测试。

// O(n)
void function1(long long n) {
    long long k = 0;
    for (long long i = 0; i < n; i++) {
        k++;
    }
}
// O(n^2)
void function2(long long n) {
    long long k = 0;
    for (long long i = 0; i < n; i++) {
        for (long j = 0; j < n; j++) {
            k++;
        }
    }
}
// O(nlogn)
void function3(long long n) {
    long long k = 0;
    for (long long i = 0; i < n; i++) {
        for (long long j = 1; j < n; j = j*2) { // 注意这里j=1
            k++;
        }
    }
}

来看一下这三个函数随着n的规模变化，耗时会产生多大的变化，先测function1 ，就把 function2 和 function3 注释掉

int main() {
    long long n; // 数据规模
    while (1) {
        cout << "输入n：";
        cin >> n;
        milliseconds start_time = duration_cast<milliseconds >(
            system_clock::now().time_since_epoch()
        );
        function1(n);
//        function2(n);
//        function3(n);
        milliseconds end_time = duration_cast<milliseconds >(
            system_clock::now().time_since_epoch()
        );
        cout << "耗时:" << milliseconds(end_time).count() - milliseconds(start_time).count()
            <<" ms"<< endl;
    }
}

来看一下运行的效果，如下图:

O(n)的算法，1s内大概计算机可以运行 5 * (10^8)次计算，可以推测一下$O(n^2)$ 的算法应该1s可以处理的数量级的规模是 5 * (10^8)开根号，实验数据如下。

O(n^2)的算法，1s内大概计算机可以运行 22500次计算，验证了刚刚的推测。

在推测一下$O(n\log n)$的话， 1s可以处理的数据规模是什么呢？

理论上应该是比 $O(n)$少一个数量级，因为$\log n$的复杂度 其实是很快，看一下实验数据。

$O(n\log n)$的算法，1s内大概计算机可以运行 2 * (10^7)次计算，符合预期。