算法复杂度(二)

一.算法复杂度

[ 来自360百科 ]算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源。应用于数学和计算机导论。同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。下面就时间复杂度和空间复杂度做出解释。

1.时间复杂度

(1)时间复杂度介绍

什么是时间复杂度，一个算法的执行时间是指算法中所有语句所执行完毕的时间总和，我们可以计算每条语句执行的时间，但是由于语句的执行速度与计算机的软，硬件（硬盘，存储控制器，界面卡，CPU）环境有很大影响，一条语句在不同设备上可能有不一样的执行时间，显然，计算语句的执行时间是非常不明智的，这时候，一个新的解决方案诞生了，既然我们想要准确得到语句的执行时间有些麻烦，何不换个角度思考问题，引入我们今天的主角，复杂度，我们只需要规定语句的复杂度，只需要知道执行语句花费的大致时间可以了（可以认为复杂度与时间成正比，时间越多，复杂度就越高）并规定一个语句执行花费的时间与语句的执行次数成正比，这便是时间复杂度。在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。

算法的时间复杂度，也就是算法的时间量度，记作：T(n)= O(f(n))。 用大写O()来体现算法时间复杂度的记法，我们称之为 大O记法。 一般情况下，随着输入规模n的增大，T(n)增长最慢的算法为最优算法。

图片来自360百科

常见的算法时间复杂度有： O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2^n) < O(n!) 复杂度对应的名称分别是：常数阶，对数阶，线性阶，二维阶，平方阶，立方阶，指数阶，乘阶阶

那么我们该如何计算一个现有算法的时间复杂度呢？只要记住下面三句话即可！

1.用常数1来取代运行时间中所有加法常数。 2.只要高阶项，舍去低阶项。 3.不要高阶项系数。

下面，用一些实例来介绍常见的时间复杂度。

(2)常数阶 O(1)

例1：

int a = 2;
int b = 3;
int temp;  	
temp = a;     //执行第一次
a = b;        //执行第一次
b = temp;     //执行第一次
//三条语句一共执行了（1+1+1）= 3次，根据第一句话，用常数1来取代运行时间中所有加法常数。
//所以3用1来代替，所以该程序执行完，时间复杂度为O(1)。

例2：

printf("hello world");  //执行第一次
printf("坚持就会有收获");//执行第一次
int sum=0;    
int n=10; 
sum=(n*(n+1))/2;//执行第一次
printf("加油！");//执行第一次
//三条语句一共执行了（1+1+1+1）= 4次，根据第一条规定，用常数1来取代运行时间中所有加法常数。
//所以4用1来代替，所以该程序执行完，时间复杂度为O(1)。

有些萌新看到这里可能会问为什么类似int sum=0的语句为什么不算执行次数，因为int sum=0这属于定义变量。并不是语句，请看文章开头的黄色句子，那么那些算作是语句呢？ 以C语言为例：

接着往下看之前，先复习一下，什么是对数，可能有人已经忘记了。 a^x = N ( a > 0 && a != 1 ) 即x为以a为底，N的对数，a叫做对数的底数，N叫做真数。

(3)对数阶 O（logn）

int sum= 1;
int n = 1000;
while (sum < n)
{
 sum = sum * 2;
}
//第一次执行：sum=1*2=2  2^1
//第二次执行：sum=2*2=4  2^2
//第三次执行：sum=4*2=8  2^3
//第四次执行：sum=8*2=16 2^4
//第X次执行：2^x=n，可得x=log2n，所以复杂度为O（logn）。

(4)线性阶 O(n)

 for (int i = 0; i < n; i++)  //执行n+1次
 {
  printf("坚持就会有结果！");   //执行n次
 }
 //n+n+1=2n+1
//由三句话可得，复杂度为O(n)。

(5)二维阶 O(nlogn)

for (int i = 0; i < n; i++)  //执行n+1次
{
while (sum < n)
{
sum = sum * 2;
}
}
//二维阶也叫线性对数阶，将对数阶 O（logn）代码循环n次便是

(6)平方阶 O(n²)

for (int i = 0; i < n; i++)
{
 for (int j = 0; j <= n; j++)
 {
  j = 1;
  j++;
 }
}
//平方阶就是把复杂度是 O(n)的代码嵌套一遍

(7)立方阶 O(n³)

//立方阶就是复杂度是 O(n)的代码嵌套两遍，这里就不再赘述。

2.空间复杂度

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

空间复杂度是一个算法在执行过程中临时占用存储空间大小的度量，记作S(n)=O( f(n) )。 常见的空间复杂度有 O(1)，O(n)，O(n^2)。

(1)常数阶 O(1)

 int i = 1; 
 int j = 2;
 ++i;
 j++;
 int m = i + j;
 //代码中的i j m变量所分配的空间都不随着处理数据量变化，因此它的空间复杂度S(n)=O(1).

(2)常数阶 O(n)

int n = 20;
int *a = new int[n];
int j;
for (int i = 1; i <= n; i++)
{
 j = i;
 j++;
}
//这段代码中，第一行new了一个数组出来，大小为n，虽然有循环，但没有分配空间。
//所以空间复杂度主要在第一行，即S(n)=O(n).

3.列出一些常用算法的时间复杂度和空间复杂度

在这里插入图片描述

4.结束语

算法复杂度是我们踏入数据结构的以及算法的第一步，在这里，我想对你们说，永远不要觉得数据结构或者算法，没有什么用，无用之用，是为大用，永远不要觉得自己可以按照需求写出来就很?了，如果你从来没有研究过自己所写代码的效率，这样的你是可悲的你。 不要闭门造车，觉得你很?，记住，永远不要这样。最后以一张图来说明算法的重要性。

在这里插入图片描述

希望身为程序员的各位，在今后的学习中，不要愚公移山，而是要好好利用现代移山的方法，好好利用算法分析的工具 ，改进自己的代码 ，让计算机轻松一点，这样你就更加胜人一筹。 引用《大话数据结构》作者：程杰

不足之处，请批评指正，欢迎一起交流讨论。 每文一句：一个人有了远大的理想，就是在最艰苦难的时候，也会感到愉悦。