算法的时间复杂度与空间复杂度---举例分析

一、 算法

算法的定义是这样的：解题方案的准确而完善的描述，是一系列解决问题的清晰指令。巴拉巴拉的，虽然是一小句但还是不想看（题外话：有时候吧专业名词记下来面试的时候还是挺有用的），其实就是解决一个问题的完整性描述。只不过这个描述就可能是用不同的方式或者说是“语言”了。

 - 算法的效率

既然算法是解决问题的描述，那么就像一千个人眼中有一千个阿姆雷特他大姨夫一样，解决同一个问题的办法也是多种多样的，只是在这过程中我们所使用/消耗的时间或者时间以外的代价（计算机消耗的则为内存了）不一样。为了更快、更好、更强的发扬奥利奥..哦不，提高算法的效率。所以很多时候一个优秀的算法就在于它与其他实现同一个问题的算法相比，在时间或空间（内存）或者时间和空间（内存）上都得到明显的降低。

所以呢，算法的效率主要由以下两个复杂度来评估：

时间复杂度：评估执行程序所需的时间。可以估算出程序对处理器的使用程度。
空间复杂度：评估执行程序所需的存储空间。可以估算出程序对计算机内存的使用程度。                                                             

设计算法时，时间复杂度要比空间复杂度更容易出问题，所以一般情况一下我们只对时间复杂度进行研究。一般面试或者工作的时候没有特别说明的话，复杂度就是指时间复杂度。

二、 时间复杂度

接下来我们还需要知道另一个概念：时间频度。这个时候你可能会说：“不是说好一起学算法吗，这些东东是什么？赠品吗？”。非也非也，这是非卖品。

因为一个算法执行所消耗的时间理论上是不能算出来的，没错正是理论上，so我们任然可以在程序中测试获得。但是我们不可能又没必要对每个算法进行测试，只需要知道大概的哪个算法执行所花费的时间多，哪个花费的时间少就行了。如果一个算法所花费的时间与算法中代码语句执行次数成正比，那么那个算法执行语句越多，它的花费时间也就越多。我们把一个算法中的语句执行次数称为时间频度。通常（ps:很想知道通常是谁）用T(n)表示。

在时间频度T(n)中，n又代表着问题的规模，当n不断变化时，T(n)也会不断地随之变化。为了了解这个变化的规律，时间复杂度这一概念就被引入了。一般情况下算法基础本操作的重复执行次数为问题规模n的某个函数，用也就是时间频度T(n)。如果有某个辅助函数f(n)，当趋于无穷大的时候，T(n)/f(n)的极限值是不为零的某个常数，那么f(n)是T(n)的同数量级函数，记作T(n)=O(f(n))，被称为算法的渐进时间复杂度，又简称为时间复杂度。

1- 大O表示法及时间复杂度举例

用O(n)来体现算法时间复杂度的记法被称作大O表示法

一般我们我们评估一个算法都是直接评估它的最坏的复杂度。

大O表示法O(f(n))中的f(n)的值可以为1、n、logn、n^2 等，所以我们将O(1)、O(n)、O(logn)、O( n^2 )分别称为常数阶、线性阶、对数阶和平方阶。下面我们来看看推导大O阶的方法：

推导大O阶

推导大O阶有一下三种规则：

1. 用常数1取代运行时间中的所有加法常数
2. 只保留最高阶项
3. 去除最高阶的常数

举好多栗子

• 常数阶

1.  
   let sum = 0, n = 10; // 语句执行一次
2.  
   let sum = (1+n)*n/2; // 语句执行一次
3.  
   console.log(`The sum is : ${sum}`) //语句执行一次

这样的一段代码它的执行次数为 3 ，然后我们套用规则1，则这个算法的时间复杂度为O(1)，也就是常数阶。

• 线性阶

1.  
   let i =0; // 语句执行一次
2.  
   while (i < n) { // 语句执行n次
3.  
   console.log(`Current i is ${i}`); //语句执行n次
4.  
   i++; // 语句执行n次
5.  
   }

这个算法中代码总共执行了 3n + 1次，根据规则 2->3，因此该算法的时间复杂度是O(n)。

• 对数阶

1.  
   let number = 1; // 语句执行一次
2.  
   while (number < n) { // 语句执行logn次
3.  
   number *= 2; // 语句执行logn次
4.  
   }

上面的算法中，number每次都放大两倍，我们假设这个循环体执行了m次，那么2^m = n即m = logn，所以整段代码执行次数为1 + 2*logn，则f(n) = logn，时间复杂度为O(logn)。

• 平方阶

1.  
   for (let i = 0; i < n; i++) { // 语句执行n次
2.  
   for (let j = 0; j < n; j++) { // 语句执行n^2次
3.  
   console.log('I am here!'); // 语句执行n^2
4.  
   }
5.  
   }

上面的嵌套循环中，代码共执行 2*n^2 + n，则f(n) = n^2。所以该算法的时间复杂度为O(n^2 )

2、常见时间复杂度的比较

常见的时间复杂度函数相信大家在大学中都已经见过了，这里也不多做解释了：

O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)<O(n!)

三、空间复杂度

2. 算法的空间复杂度

我们在写代码时，完全可以用空间来换去时间。
举个例子说，要判断某年是不是闰年，你可能会花一点心思来写一个算法，每给一个年份，就可以通过这个算法计算得到是否闰年的结果。
另外一种方法是，事先建立一个有2050个元素的数组，然后把所有的年份按下标的数字对应，如果是闰年，则此数组元素的值是1，如果不是元素的值则为0。这样，所谓的判断某一年是否为闰年就变成了查找这个数组某一个元素的值的问题。

第一种方法相比起第二种来说很明显非常节省空间，但每一次查询都需要经过一系列的计算才能知道是否为闰年。第二种方法虽然需要在内存里存储2050个元素的数组，但是每次查询只需要一次索引判断即可。

这就是通过一笔空间上的开销来换取计算时间开销的小技巧。到底哪一种方法好？其实还是要看你用在什么地方。

2.1 算法的空间复杂度定义

算法的空间复杂度通过计算算法所需的存储空间实现，算法的空间复杂度的计算公式记作：S(n)=O(f(n))，其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数，也是一种“渐进表示法”，这些所需要的内存空间通常分为“固定空间内存”（包括基本程序代码、常数、变量等）和“变动空间内存”（随程序运行时而改变大小的使用空间）

通常，我们都是用“时间复杂度”来指运行时间的需求，是用“空间复杂度”指空间需求。
当直接要让我们求“复杂度”时，通常指的是时间复杂度。

2.2 计算方法

 忽略常数，用O(1)表示 
    递归算法的空间复杂度=递归深度N*每次递归所要的辅助空间 
    对于单线程来说，递归有运行时堆栈，求的是递归最深的那一次压栈所耗费的空间的个数，因为递归最深的那一次所耗费的空间足以容纳它所有递归过程。

1.  
   a = 0
2.  
   b = 0
3.  
   print(a,b)

它的空间复杂度O（n）=O（1）;

1.  
   def fun(n):
2.  
   k = 10
3.  
   if n == k:
4.  
   return n
5.  
   else:
6.  
   return fun(++n)

递归实现，调用fun函数，每次都创建1个变量k。调用n次，空间复杂度O（n*1）=O（n)。

1.  
    
2.  
   for(i=0;i<n;++):
3.  
    
4.  
   temp = i

变量的内存分配发生在定义的时候，因为temp的定义是循环里边，所以是n*O(1)

1.  
    
2.  
   temp=0;
3.  
    
4.  
   for(i=0;i<n;i++):
5.  
    
6.  
   temp = i

temp定义在循环外边，所以是1*O(1)

四、时间复杂度与空间复杂度比较

1、常用算法的时间复杂度和空间复杂度

2、时间复杂度为主，空间复杂度为辅

考虑复杂度的话，“程序本身所占的空间”你可以忽略，因为这是“算法的描述”部分，这部分就是个常量（你的程序代码段写完就固定大小了），算上它也只是加一个常数

“输入数据所占的存储空间”这个其实可以算“需要多少空间”，但不一定是“访问到多少空间”，如果算上这块，那么所有算法的空间复杂度至少是O(N)，就像如果你计算读入输入的时间的话，所有算法的时间复杂度至少也是O(N)一样，比如说二分查找，虽然你需要O(N)的空间存储所有数据，但是每次查找只需要O(lgN)次操作和访问，也就是说访问到的空间撑死也就是O(lgN)，一个算法的所有操作涉及到的空间的复杂度不会超出其时间复杂度，时间复杂度已经给出了一个上界了，这也是平时不怎么关注空间复杂度的一个原因

第三个“算法执行过程中所需的存储空间”可以认为是算法的额外需要的空间，这个可能有也可能没有，具体算法具体分析了，但就像上面说的，它也不会超出时间复杂度的上界