时间复杂度和空间复杂度及多道例题讲解

为什么会有复杂度这个概念呢？原因是算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源。因此

衡量一个算法的好坏，一般

是从时间和空间两个维度来衡量的

，即时间复杂度和空间复杂度。

时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间（是额外开辟的空间不包括本身已有的空间）

。在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。

1.先来了解一下时间复杂度的概念

在计算机科学中，

算法的时间复杂度是一个函数

，它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知

道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，

算法中的基本操作的执行次数，为算法

的时间复杂度。

即：找到某条基本语句与问题规模N之间的数学表达式，就是算出了该算法的时间复杂度。

下面来看例题：

void Func1(int 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*N也就是N^2，还有一个for循环的次数是2*N，while循环中又会循环10次，所以总的时间复杂度为N^2+2N+10，而在数据结构中计算时间复杂度用的是大O的渐进表示法，此方法是计算大概执行次数。以下是大O表示法的使用规则：

大

O

符号（

Big O notation

）：是用于描述函数渐进行为的数学符号。

推导大

O

阶方法：

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

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

3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。

我们以上面例题为例子，在修改后的运行次数函数中，只保留最高阶项，所以我们保留N^2，N^2的系数去除，所以最后表示出来为O（N^2）；

用常数1取代运行时间中的所有加法常数。这句话是什么意思呢？其实就是当循环为k<100时，这是次数是常数100这样的时间复杂度用O（1）表示。

我们来练习几道例题：

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

2N+10去掉常数项10拿掉最高高阶项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);
}

第三题：

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

很明显K<100次数为常数次，所以时间复杂度为O（1）；

第四题：

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

要计算冒泡排序的复杂度我们要先知道冒泡排序的原理，冒泡排序是将要排序的数依次比较移动到最前或最后一个位置，一趟冒泡排序可以将1个数换到指定顺序的位置，总次数是n-1趟原因是如果有10个数要排序那么排9个数剩下一个数的位置自己就被换到相应的位置。而在每一趟中排完一个数后就减少1次，所以每一趟的次数是N-1,N-2,N-3……1,而一趟冒泡排序的次数又是N-1，所以时间复杂度是(N-1)*(N-1）为O（N^2），为什么要用N-1不用N-2或者后面的计算呢？原因是时间复杂度计算的是最差的结果。

第五题：

int BinarySearch(int* a, int n, int x)
{
 assert(a);
 int begin = 0;
 int end = n-1;
 // [begin, end]：begin和end是左闭右闭区间，因此有=号
 while (begin <= end)
 {
 int mid = begin + ((end-begin)>>1);
 if (a[mid] < x)
 begin = mid+1;
 else if (a[mid] > x)
 end = mid-1;
 else
 return mid;
 }
 return -1;
}

要计算二分查找法的时间复杂度首先要明白其原理，二分查找就是根据中间值看下次查找的区间在中间值的左边还是右边，明天这个我们就知道每次查找的次数都会除2，比如有N个数，那么要找到这个数就需要N/2/2/2/2/2…,假设查找了X次，N=2*2*2*2*2*2(乘2的x次方）也就是N=2^X，X=log2N（log以2为底N的对数）所以二分查找的时间复杂度为O（logN）由于计算机不好打出以2为底所以直接为logN，当有底数不是2的时候需要写出底数.

第六题：

long long Fac(size_t N)
{
 if(0 == N)
 return 1;
 
 return Fac(N-1)*N;
}

计算阶乘的时间复杂度，每次N递归从N-1,N-2,N-3,N-4….0,很多人将此复杂度错误认为N^2，其实在这里每次递归乘的N都只是一个常数比如N为10的时候F（9）*10然后F（9）为F（8）*10一直往下递归，在这我们就能看出来时间复杂度是O（N）；

第七题：

long long Fib(size_t N)
{
 if(N < 3)
 return 1;
 
 return Fib(N-1) + Fib(N-2);
}

计算斐波那契数列的时间复杂度我们需要画个图：

如图我们可以看出斐波那契数列的时间复杂度为O（2^N）。

第八题：

设某算法的递推公式是T(n)=T(n-1)+n，T(0)=1，则求该算法中第n项的时间复杂度为

此题与阶乘类似，每次递归的是T（n-1）对于加的常数不做处理，从n-1,n-2,n-3……0所以时间复杂度为O(N).

第八题：

给定一个整数sum，从有N个有序元素的数组中寻找元素a，b，使得a+b的结果最接近sum，最快的平均时间复杂度是

此题计算的是最快的时间复杂度，那么在一个有序数组中找接近SUM的和我们只需要两个指针一个从头开始一个从尾开始一起遍历，那么最快就是O（N）。

第九题：

void fun(int n) {
  int i=l;
  while(i<=n)
    i=i*2;
}

在while循环中终止的条件是i<=n,而i以2的次方的形式增加，我们假设2的x次方后循环结束，2^x=n，x=log2N(以2为底N的对数）所以时间复杂度为O（logN）.

2.空间复杂度

空间复杂度也是一个数学表达式，是对一个算法在运行过程中

临时占用存储空间大小的量度

。

空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似，也使用

大

O

渐进表示法

。

注意：

函数运行时所需要的栈空间

(

存储参数、局部变量、一些寄存器信息等

)

在编译期间已经确定好了，因

此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。

由于计算空间复杂度非常简单，所以我们直接来看题：

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

在冒泡排序中使用的额外空间有end exchange i三个变量的空间，所以空间复杂度为O（1）；

long long* Fibonacci(size_t n)
{
 if(n==0)
 return NULL;
 
 long long * fibArray = (long long *)malloc((n+1) * sizeof(long long));
 fibArray[0] = 0;
 fibArray[1] = 1;
 for (int i = 2; i <= n ; ++i)
 {
 fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
 }
 return fibArray;
}

第二题：

long long* Fibonacci(size_t n)
{
 if(n==0)
 return NULL;
 
 long long * fibArray = (long long *)malloc((n+1) * sizeof(long long));
 fibArray[0] = 0;
 fibArray[1] = 1;
 for (int i = 2; i <= n ; ++i)
 {
 fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
 }
 return fibArray;
}

由图可知一开始开辟了n+1个（long long）大小的空间，后面没有再开辟另外的空间所以空间复杂度为O（N）。

第三题：

long long Fac(size_t N)
{
 if(N == 0)
 return 1;
 
 return Fac(N-1)*N;
}

在计算阶乘中只需要开辟N个栈帧，因为空间会重复利用如图所示，计算N-1的时候开辟一个空间，N-1又递归N-2又开辟一个空间。

所以空间复杂度为O（N）。

第四题：

int** fun(int n) {
    int ** s = (int **)malloc(n * sizeof(int *));
    while(n--)
      s[n] = (int *)malloc(n * sizeof(int));
    return s;
  }

首先**s开辟了n个大小为（int*）的空间，然后再刚刚给s开辟的空间的内部又给变量开辟了n个大小为（int）的空间，类似于两个for循环嵌套，所以时间复杂度为O（N^2）。此处开辟的是一个二维数组，数组有n行，每行分别有1,2,3,…n列，所以是n(n + 1)/2个元素空间。

你可能也喜欢