一, 什么是算法
算法:
一个有限指令集
接受一些输入(有些情况下不需要收入)
产生输出
一定在有限步骤之后终止
每一条指令必须:
有充分明确的目标, 不可以有歧义
计算机能处理的范围之内
描述应不依赖于任何一种计算机语言以及具体的实现手段
其实说白了, 算法就是一个计算过程解决问题的方法. 我们现在已经知道数据结构表示数据是怎么存储的, 而 "程序 = 数据结构 + 算法", 数据结构是静态的, 算法是动态的, 它们加起来就是程序.
对算法来说有输入, 有输出, 相当于函数有参数有返回值. 我们写算法的时候习惯把算法封装到一个函数中.
二, 什么是好的算法
好, 从上面我们知道了什么是算法, 下面我再说什么是好的算法?
在解决同一个问题的时候, 我们通常会有很多种不一样的算法, 区别就在于, 有的算法比较笨, 有的算法比较聪明, 那我们怎么去衡量它们谁好谁坏呢? 我们通常有下面两个指标:
空间复杂度: 根据算法写成的程序在执行时占用存储单元的长度.
时间复杂度: 根据算法写成的程序在执行时耗费时间的长度.
先举个例子说, 如果让你打印十个整数, 你那个程序可能瞬间就给出结果了, 如果让你打印十万个整数呢? 这你就得多等一会了. 所以这个程序运行的时间, 就跟你要处理的数据是十个还是十万个是相关的, 这个十或十万就是我们要处理的数据的规模. 我们把它叫做 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(1), 首先 print('Hello World')打印一次和打印三次实际的影响不大吧, 就是不管执行几次, 只要它的规模不上升到 n 这么大的时候, 换句话说, 1 是个单位, 所以不管怎样, 因为这是表示近似, 不是表示精确的, 所以是 O(1). 好, 再看下面这个图片:
当你的循环减半的时候, 时间复杂度就会变为 O(logn). 所以你可以这样记, 当算法过程出现循环折半的时候, 复杂度式子中会出现 logn.
时间复杂度小结
时间复杂度是用来估计算法运行时间的一个式子(单位)
一般来说, 时间复杂度高的算法比时间复杂度低的算法慢
常见的时间复杂度(按效率排序)
复杂问题的时间复杂度
如何简单快速地判断算法复杂度
空间复杂度
在空间复杂度中需要注意的一点就是理解 "空间换时间", 在研究一个算法的时候, 时间比空间重要.
此篇完
来源: https://www.cnblogs.com/zyx110/p/11852975.html