时间复杂度介绍

程序运行的时候会消耗时间资源和空间（内存）资源，因此衡量一个算法的好坏，可以从时间复杂度和空间复杂度来看。

时间复杂度： 算法的时间复杂度是一个函数，它定量的描述了算法的运行时间。算法中基本操作的执行次数为算法的时间复杂度。我们一般不需要精确的知道一个程序的执行次数，也只需要大概估计出次数，这里我们一般用大O的渐进表示法

大O的渐进表示法

首先大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。

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

例如：执行常数次（1,100或者1000），表示为O(1)

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

例如： 执行(N^2 +N)次， 表示为O(N^2)

3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数，得到的便是大O的渐进表示法

例如： 执行 (N*(N+1)/2）次， 表示为O（N^2）

有些算法的时间复杂度存在最好、平均和最坏情况：

最坏情况：任意输入规模的最大运行次数(上界)

平均情况：任意输入规模的期望运行次数

最好情况：任意输入规模的最小运行次数(下界)

例如：在一个长度为N数组中搜索一个数据x

最好情况：1次找到

最坏情况：N次找到

平均情况：N/2次找到

在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)。

实例

实例一（循环）

void Func3(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);
}

两个for循环， 一个循环执行M次，另一个执行N次，

所以精确的次数就为：（M+N）

大O的渐进表示法

由于M和N都是未知数，

第一种：如果没有说明M和N的大小关系，O(M+N)

第二种：如果M >> N，O(M)

第三种：如果M<<, O(N)

第四种：如果M和N差不多大小， O(M) 或者O(N)

实例二（嵌套循环）

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

一个for循环的嵌套,执行次数N^2,后面一个for,2N次，后面一个while,执行次数10次。

精确次数：N^2+2N+10

大O渐进表示法：O(N^2)

实例三（冒泡排序）

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次，第二趟比较N - 2 次， 第三趟比较 N - 3次，…一直到第N - 1趟， 比较1次。

所以执行的精确次数 = N - 1 + N - 2+ N - 3+ N - 4+ N - 5+ ……1(就是个等差数列求和) = N(N - 1)/2*

大O的渐进表示法：N^2

实例四（二分法）

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;
}

首先，我们必须要明白算时间复杂度，我们不能去看它是几层循环，而是要去看它的思想。

二分法：是从左边和右边，向中间找，最好的情况：自然是一次就找到了，但是时间复杂度，是要考虑最坏的情况，第一没找到的话，便会在左边一半中找，或者是在右边的一半中寻找，就这样一直找，直到找到为止，所以每找一次，便是2（可以想象折纸反过来展开的过程）。

最好的情况：O(1)

最坏的情况(一般考虑最坏的情况)：如果查找次数为x次，找一次就是2， 12222 … = N

–> 2^x = N —> x = log2(2为底)N -->O(log以2为底N的对数)