怎样才是一个好算法：空间复杂度 & 时间复杂度
大家好，欢迎来到 Crossin的编程教室 ！
“算法”是一个我们经常在编程学习、求职面试时听到的一个词。那么，什么是算法？以及如何评价一个算法的好坏？今天我们就来给大家说一说。
一、什么是算法
算法：
一个有限指令集
接受一些输入(有些情况下不需要收入)
产生输出
一定在有限步骤之后终止
每一条指令必须：
有充分明确的目标，不可以有歧义
计算机能处理的范围之内
描述应不依赖于任何一种计算机语言以及具体的实现手段
其实说白了，算法就是一个计算过程解决问题的方法。我们现在已经知道数据结构表示数据是怎么存储的，而“程序=数据结构+算法”，数据结构是静态的，算法是动态的，它们加起来就是程序。
对算法来说有输入，有输出，相当于函数有参数有返回值。我们写算法的时候习惯把算法封装到一个函数中。
二、什么是好的算法
好，从上面我们知道了什么是算法，下面我再说什么是好的算法？
在解决同一个问题的时候，我们通常会有很多种不一样的算法，区别就在于，有的算法比较笨，有的算法比较聪明，那我们怎么去衡量它们谁好谁坏呢？我们通常有下面两个指标：
空间复杂度:根据算法写成的程序在执行时占用存储单元的长度。
时间复杂度：根据算法写成的程序在执行时耗费时间的长度。
先举个例子说，如果让你打印十个整数，你那个程序可能瞬间就给出结果了，如果让你打印十万个整数呢？这你就得多等一会了。所以这个程序运行的时间，就跟你要处理的数据是十个还是十万个是相关的，这个十或十万就是我们要处理的数据的规模。我们把它叫做n，是一个变量的话，那我们这个程序所用的时间和空间都跟这个n是有直接关系的。解决一个问题有很多中不同的方法，你在设计这个方法的时候，一定要把这两个要素考虑清楚。一不小心，如果空间复杂度太大的话，你那个程序就可能直接爆掉了，非正常中断，我一会会在后面讲，时间复杂度如果太大的话，你就可能等很长时间都等不出结果。
时间复杂度
先来看上面图片中的几组代码，我是用Python表示的，你在看的时候考虑两个问题：
四组代码中，哪组的运行时间最短？
用什么方式来体现算法运行的快慢？
刚才说n可以看作数据的规模，规模不一样，运行时间肯定也不一样，而且所用时间也不好确定，不同的n会得到不同的时间，所以我们用时间复杂度来表示算法运行的快慢。
先来看下面图片中的几个生活中的事件，估计时间：
这里你会发现我们会用“几”表示一个大概，后面还有相应的时间单位，那时间复杂度也参照类似的方法：
时间复杂度：用来评估算法运行效率的一个式子
看上面图片所示，先说print(‘Hello World’),它的时间复杂度表示为O(1),O严格来说，它表示数学上一个式子的上界，我们可以简单的理解为就是一个估计，大约，相当于上面说的“几”。1可以理解为是个运行单位(类似于秒这样的单位)，为什么是O(1)，因为print(‘Hello World’)只执行了一次，同理分析第二个：
for i in range(n):
print('Hello World')
它的时间复杂度表示为O(n)，因为这组代码执行了n次。n还是个单位，同理，分析第三个：
for i in range(n): for j in range(n): print('Hello World')它的时间复杂度表示为O(
),因为是有两层循环，所以是
,
还是个单位。第四个你自己就可以分析了，我就不多此一举了。但千万不要以为就是这么简单，咱再看下面代码图片：
看到这个图片，你是不是感觉很良好，和你猜的差不多是吧，哈哈，不要高兴的太早，告诉你们，错了，它们的时间复杂度不是这样的。
为什么？我说了，“1”是单位，但“3”不是单位，3是3乘1，就比如说在生活中，问你一壶水烧多长时间，没有人回答说是三个几分钟或者几个三分钟。再说第二个，
是单位，n也是个单位，但是
比n大，所以我们在估计时用大单位，就好比生活中问你大概睡了多久，你一般说是几个小时，而不是说几个小时零几分钟，你强调的是一个大概的时间，明白了吧。
所以正确的时间复杂度是这样的：
当你的循环减半的时候，时间复杂度就会变为O(logn)。所以你可以这样记，当算法过程出现循环折半的时候，复杂度式子中会出现logn。
时间复杂度小结
时间复杂度是用来估计算法运行时间的一个式子(单位)
一般来说，时间复杂度高的算法比时间复杂度低的算法慢
常见的时间复杂度(按效率排序)
复杂问题的时间复杂度
如何简单快速地判断算法复杂度
空间复杂度
在空间复杂度中需要注意的一点就是理解“空间换时间”，在研究一个算法的时候，时间比空间重要。毕竟，你的时间要比你的内存更值钱