C语言数据结构通关时间复杂度和空间复杂度

算法的时间复杂度和空间复杂度

一、时间复杂度：

首先，为什么会有这个概念的出现呢？

原来啊，在进行算法分析时，语句总的执行次数T（n）是关于问题规模n的函数，进而分析T（n）随n的变化情况并确定T（n）的数量级。算法的时间复杂度，也就是算法的时间量度，记作T（n） = O（f（n））。它表示随问题规模n的增大，算法执行时间的增长率和f（n）的增长率相同，称作算法的渐进时间复杂度，简称为时间复杂度，其中f（n）是问题规模n的某个函数。

这样用大写O（）来体现算法时间复杂度的记法，称为大O记法。

你可以简单这样认为：算法时间复杂度实际上就是基本操作的执行次数。

到这里，我们先来谈谈如何推导大O阶方法

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

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

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

得到的结果就是大O阶

这仿佛就像是游戏攻略一样，我们得到了一个推导算法时间复杂度的万能公式。可是实际上，分析一个算法的时间复杂度，没有这么的简单。

按照算法时间复杂的定义，我们取了非官方的名称，常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2)，立方阶O(n3),...， k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。下面我们对其分析分析。

1.常数阶

我们随便给几行代码

int sum = 0,n = 100；
sum = (1+n)*n/2；
printf("%d",sum)；

大声回答这个算法时间复杂度是O（3）还是O（1），答案肯定是O（1）啊，首先这个算法执行次数函数是f（n） = 3；根据我们推导大O阶的方法，把3改为1，这是常数项，没有其他项可，所以是O（1）。实际上无论n是多少，这种与问题的大小无关，执行时间恒定的算法，我们称为具有O（1）的时间复杂度，又叫常数阶。

注意：不管这个常数是多少，我们都记作O（1），而不是O（3），O（5）等其他数字，这是初学者常犯的错误。

2.线性阶

线性阶的循环结构会复杂很多。要确定某个算法的阶次，我们需要确定某个特定语句运行的次数。

下面这段代码，它的循环的时间复杂度为O（n），因为循环体中的代码需要执行n次

int i;
for(i=0;i<n;i++)
{
/*时间复杂度为O（1）的程序步骤序列*/
}

3.对数阶

下面这段代码，时间复杂度又是多少呢？

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

由于每次count乘以2以后，就距离n更近了一分，也就是说，有多少个2相乘后大于n，则会退循环。有2的x次方＝n，x = log2n。所以这个循环的时间复杂度为O（longn）

4.平方阶

下面例子是一个循环嵌套，它的内循环刚才我们已经分析过。时间复杂度为O（n）

int i,j;
for(i=0;i<n;i++)
{
  for(j=0;j<n;j++)
  {
    /*时间复杂度为O（1）的程序步骤序列*/
  }
}

而对于外层的循环，不过是内部这个时间复杂度为O（n）的语句，在循环n次。所以时间复杂度为O（n*n）；如果外层循环次数改为了m，那时间复杂度就为O（m*n）

所以我们可以总结得出，循环的时间复杂度等于循环体的复杂度乘以该循环运行的次数。那么下面这个循环嵌套，它的时间复杂度是多少呢？

int i,j;
for(i=0;i<n;i++)
{
for(j=i;j<n;j++)/*注意j=i而不是o*/
{
/*时间复杂度为O（1）的程序步骤序列*/
}
}

由于当i=0是，内循环执行了n次，当i=1时，执行了n-1次，.......当i=n-1是，执行了1次。所以总的执行次数为n+（n-1）+（n-2）+....+1 = n（n+1）/2 = n*n/2+n/2；根据大O阶推导的方法。最终这段代码的时间复杂度为O（n*n）。

从这个例子我们可以知道，理解大O阶推导不算难，难的是对数列的一些相关运算，这更多的是考察你的数学知识和能力，我们继续看例子。

对于方法调用的时间复杂度又如何分析。

int i，j;
for(i = 0;i<n;i++)
{
function(i);
}

上面这段代码调用一个函数function（）

void function(int count)
{
print(count);
}

函数体是打印count这个参数。这很好理解。function（）函数的时间复杂度是O（1）。所以整体的时间复杂度为O（n）

常用的时间复杂度所耗费的时间从小到大依次是：

Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)

实际上，对于算法的分析，一种方法时候计算所有情况的平均值，这中时间复杂度的计算方法称为平均时间复杂度。另一种方法是计算最坏情况下的时间复杂度，这种方法称为最坏时间复杂度。一般在没有特殊说明的情况下，都是指最坏时间复杂度。

二、空间复杂度

类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的，是通过参数表由调用函数传递而来的，它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比，要压缩这方面的存储空间，就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异，有的算法只需要占用少量的临时工作单元，而且不随问题规模的大小而改变，我们称这种算法是“就地\"进行的，是节省存储的算法，如这一节介绍过的几个算法都是如此；有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元。

看了这个标准官方的定义后，是不是有一点点小小的理解。

我们在写代码时，完全可以用空间来换取时间，比如判断某某年是不是闰年这个问题的解决。就可以存储空间来换取计算时间的小技巧。通常我们都使用“时间复杂度”来指运行时间的需求，使用“空间复杂度”指空间需求。当不用限定词地使用“复杂度”时，通常都是指空间复杂度。

言外之意，我们这里不重点讲解时间复杂度了。

通过以上的介绍，想必对时间复杂度与空间复杂度都了了自己的认识了把，本次的博客也到此结束。