导航

本文有点长,没错.是有点长

• 算法及解释

• 时间复杂度

• 数据结构和时间复杂度对比表

• JS实现

• PHP实现

算法及解释

百度百科中对于算法解释,我表示一脸懵逼.

算法分为5个步骤.有穷性(有限性)->确切性->输入->输出->可行性

浅显的解释就是: 我希望不费脑的读完这篇文章明白尽量多的知识(空间复杂度).或者快速读完这篇文章就完全明白作者讲的是什么(时间复杂度)

上面提到两个非常重要的概念.时间复杂度和空间复杂度.它是比较算法在你应用中适用与否选择的侧重点

如同本文.我们想要的结果是获得更多知识.这是评价文章好坏的结果.也是文章最终的结果(输出)

解释得越详细.你不管花多少时间就是需要明白.篇幅大占用的空间就大.这就是空间复杂度.因为你不在乎时间.

如果你在乎时间.那么文章篇幅必须小且精简.这就是时间复杂度

这是很逗比的解释.它当然不会那么简单.现在我要学习很多知识呢?比如JAVA,PHP,JS,甚至还想跟加藤鹰老师学习(有穷性(有限性)..你不可能什么都想学吧!)?那么相应的时间复杂度和空间复杂度就不是单一的线性表示,就需要一个公式来计算我到底需要多少时间才快速学习完这些知识(确切性..表示我学这些买一个步骤都是有意义,1+1=2).这里就不解释空间复杂度了,因为你的硬盘那么大,你会在乎电影多?

时间复杂度

指执行算法所需要的计算工作量。一般来说，计算机算法是问题规模n 的函数f(n)，算法的时间复杂度也因此记做 : T(n)=Ο(f(n))，问题的规模n 越大，算法执行的时间的增长率与f(n) 的增长率正相关.也称渐近时间复杂度，简称为时间复杂度，其中f(n) 是问题规模 n 的某个函数。

常见的时间复杂度

1.常数级复杂度 O(1)

2.对数级复杂度 O(logN)

3.线性级复杂度 O(n)

4.线性对数阶级复杂度 O(NlogN)

5.平方级复杂度 O(N^2)

6.立方O(N^3)

7.指数阶O(2^N)

时间复杂度所耗费时间从小到大依次是:

O(1) < O(logn) < (n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

js 代码示例时间复杂度:

O(1) : 只执行了一次.比如数组查找 arr.apple或者arr[1]

O(logN) 又或是O(log2N) : 执行了四次.比如二分结构算法将常数对分计算

O(n) : 执行了八次.比如数组遍历

O(NlogN) : 循环内嵌套循环.

数据结构和时间复杂度对比表

常用数据结构的时间复杂度对比

数据结构	时间复杂度
	索引	查找	插入	删除	索引	查找	插入	删除
基本数组	O(1)	O(n)	–	–	O(1)	O(n)	–	–
动态数组	O(1)	O(n)	O(n)	O(n)	O(1)	O(n)	O(n)	O(n)
单链表	O(n)	O(n)	O(1)	O(1)	O(n)	O(n)	O(1)	O(1)
双链表	O(n)	O(n)	O(1)	O(1)	O(n)	O(n)	O(1)	O(1)
跳表	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(n)	O(n)	O(n)	O(n)
哈希表	–	O(1)	O(1)	O(1)	–	O(n)	O(n)	O(n)
二叉搜索树	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(n)	O(n)	O(n)	O(n)
笛卡尔树	–	O(log(n))	O(log(n))	O(log(n))	–	O(n)	O(n)	O(n)
B-树	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))
红黑树	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))
伸展树	–	O(log(n))	O(log(n))	O(log(n))	–	O(log(n))	O(log(n))	O(log(n))
AVL 树	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))

排序算法

算法	数据结构	时间复杂度	最坏情况下的辅助空间复杂度
		最佳	平均	最差	最差
快速排序	数组	O(n log(n))	O(n log(n))	O(n^2)	O(n)
归并排序	数组	O(n log(n))	O(n log(n))	O(n log(n))	O(n)
堆排序	数组	O(n log(n))	O(n log(n))	O(n log(n))	O(1)
冒泡排序	数组	O(n)	O(n^2)	O(n^2)	O(1)
插入排序	数组	O(n)	O(n^2)	O(n^2)	O(1)
选择排序	数组	O(n^2)	O(n^2)	O(n^2)	O(1)
桶排序	数组	O(n+k)	O(n+k)	O(n^2)	O(nk)
基数排序	数组	O(nk)	O(nk)	O(nk)	O(n+k)

堆

Heaps	时间复杂度
	建堆	查找最大值	提取最大值	Increase Key	插入	删除	合并
链表 （已排序）	–	O(1)	O(1)	O(n)	O(n)	O(1)	O(m+n)
链表（未排序）	–	O(n)	O(n)	O(1)	O(1)	O(1)	O(1)
二叉堆	O(n)	O(1)	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(m+n)
二项堆	–	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))
斐波那契堆	–	O(1)	O(log(n))*	O(1)*	O(1)	O(log(n))*	O(1)

图

节点 / 边 管理	Storage	Add Vertex	Add Edge	Remove Vertex	Remove Edge	Query
邻接表	O(|V|+|E|)	O(1)	O(1)	O(|V| + |E|)	O(|E|)	O(|V|)
关联表	O(|V|+|E|)	O(1)	O(1)	O(|E|)	O(|E|)	O(|E|)
邻接矩阵	O(|V|^2)	O(|V|^2)	O(1)	O(|V|^2)	O(1)	O(1)
关联矩阵	O(|V| ⋅ |E|)	O(|V| ⋅ |E|)	O(|V| ⋅ |E|)	O(|V| ⋅ |E|)	O(|V| ⋅ |E|)	O(|E|)

搜索

算法	数据结构	时间复杂度	空间复杂度
		平均	最差	最差
深度优先搜索 (DFS)	Graph of |V| vertices and |E| edges	-	O(|E| + |V|)	O(|V|)
广度优先搜索 (BFS)	Graph of |V| vertices and |E| edges	-	O(|E| + |V|)	O(|V|)
二分查找	Sorted array of n elements	O(log(n))	O(log(n))	O(1)
穷举查找	Array	O(n)	O(n)	O(1)
最短路径-Dijkstra，用小根堆作为优先队列	Graph with |V| vertices and |E| edges	O((|V| + |E|) log |V|)	O((|V| + |E|) log |V|)	O(|V|)
最短路径-Dijkstra，用无序数组作为优先队列	Graph with |V| vertices and |E| edges	O(|V|^2)	O(|V|^2)	O(|V|)
最短路径-Bellman-Ford	Graph with |V| vertices and |E| edges	O(|V||E|)	O(|V||E|)	O(|V|)

JS实现

冒泡排序

遍历排列的数列.依次比较两个元素.如果顺序错误(左小右大为正确)就把他们交换过来.不停遍历到不需要交换为止(数列已经排序完成,越小的数会不停交换浮现到数组左边)

选择排序

在未排序的数列中找到最小(或大)放在排序序列的开始(或结束)位置.然后从剩下的序列中继续寻找最小(或大)元素,放到已经排序的序列中末尾.直到所有元素排列完成.适用于数据规模小的排序算法.因为任何数据都是O(N2)的时间复杂度,好处就是不占用额外内存

插入排序

通过构建有序序列.对于未排序数据.在已排序序列向前扫描.找到相应位置并插入.插入排序在实现上采用in-place排序(只需要用到O(1)的额外空间排序),因而在向前扫描中,需要反复把已排序元素向后挪位.为新元素提供插入位置

希尔排序

核心在于间隔序列的设定.即可用提前设定好间隔序列,也可以动态定义间隔序列.希尔排序的简单插入排序的改进版,他和排序不同之处在于他会优先比较较远的元素.希尔排序又叫缩小增量排序

解释: 根据增量值跳过序列来进行对比.增量初始化值应该合理分配(小则分配小.大分配大).

算法分析 : 突破了O(n^2)的排序算法.因为根据动态增量来跳过数列.类似于二分排序

归并排序

归并采用分治法,归并是一种稳定算法,将已经有序的子序列合并,得到完全有序的序列.即先使每个子序列有序再将有序列合并,称为2路归并.归并排序性能不受输入数据影响,但表示比选择排序好,始终都是O(NlonN)的时间复杂度.代价是额外内存.即空间复杂度

快速排序

通过一次排序将待排序记录分隔成独立两部分,其中一部分的数据均比另一部分小.则可分别对这两部分记录继续进行排序.以达到整个序列有序.是最快的排序方法

堆排序

利用堆这种数据结构设计的一种排序算法.堆积是一个近似完全二叉树的结构,并同时满足堆积的性质: 即子结点的键值或索引总是小于（或者大于）它的父节点。

计数排序

计数排序是一种稳定算法.使用一个额外数组C,其中第i个元素是数组A待排序数组中等于i元素的个数,然后根据数组C将A中的元素排到正确位置,它只能对整数且数值必须有确定范围的数组排序

桶排序

桶排序假设输入数据均匀分布.将数据分到有限的桶里.将桶里的数据分别进行排序(可以是任何算法或递归调用).桶排序是计数排序的升级版,它使用函数的映射关系.高效与否在于函数映射的确定

解释: 比如存在数组 [ 1,2,2,5]

那么会创建5个桶(依赖数组中最大数).[0,1,2,3,4,5].在采用计数算法表示.[0,1,2,0,0,1].因为存在1和2个2和5.下标就是这样表示在遍历出来即可

基数排序

基数排序是按照低位先排序.然后收集.再按照高位排序.再收集.以此类推.直到最高位.有些属性是有优先级顺序的,先按低优先级排序再排序高优先级.

基数排序基于分别排序.分别收集.所以是稳定的.基数排序也是非比较的的排序算法.从低位开始,复杂度为O(kn).k为数组中最大位数

适用于数据范围小的数组

PHP实现

---

总结 :

算法是前辈们的呕心沥血.更是数学在计算中的精粹.请尊重程序员.PHP是世界上最好的语言~