时间复杂度与空间复杂度
本文宗旨带你快速学习或者回顾大学时逃的算法课
时间复杂度表示算法的执行时间与数据规模之间的增长关系。
空间复杂度表示算法的存储空间与数据规模之间的增长关系。
本文所说的都是指平均复杂度,本文代码均为js代码(偏前端)
基础案列
/**
*时间复杂度为O(n)
*空间复杂度为O(n)
*/
var arr = [];
for(var i = 0;i < n;++i){
...
arr.push(i);
}
/**
*时间复杂度为O(n^2)
*空间复杂度为O(1)
*/
for(var i = 0;i < n;++i){
for(var j = 0;j < n;++j){
...
}
}
查找算法
猜数字游戏:在一个有序递增的number类型数组中,是否存在某个数?
- 思路一:遍历数组比较每一个元素,直至找到该元素。该算法时间复杂度为O(n)
- 思路二:二分法查找,取数组中中间元素比对大小,若小于该元素则在左侧数组中取中间元素再次比较,大于该元素则取右侧数组,直至找到该元素或左右数组为空为止。该算法时间复杂度为O(log(n))
比较快排的空间复杂度
这里先简单介绍一下快速排序思想后面会分析:选取数组中任意一个元素作为基准,遍历数组将大于基准的元素放置数组左侧,小于则放置右侧,在将左侧元素和右侧元素按照以上方式继续排列,直到你需要操作的左右侧素组元素个数为1时排序结束。(这个地方不了解快排的可以先跳过)
了解快排的同学基本都知道它的时间复杂度为O(nlog(n)),空间复杂度为O(1)的原地排序,直到有一天我看见阮一峰的一篇博客,这里我贴一下代码:
var quickSort = function(arr) {
if (arr.length <= 1) { return arr; }
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex, 1)[0];
var left = [];
var right = [];
for (var i = 0; i < arr.length; i++){
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left).concat([pivot], quickSort(right));
};
该算法的空间复杂度居然是O(nlog(n)),但是他在逻辑上比正统的快排要简单不少;
基础数据结构一
简单了解了一下时间与空间复杂度,我们来看一下基本数据结构。
线性表
线性表特点:线性表上的数据最多只有前和后两个方向(因为这篇文章我想以最简单易懂的方式表述所以尽量不写专业性比较强的词汇)
数组
数组支持随机访问元素,但是插入与删除操作较麻烦,我们大致来看看数组在计算机中的存储结构:
-
如何理解随机访问??
每个元素存储在计算机上都对应着一个地址,计算机通过地址来访问内存中的数据,所谓随机访问就是它能够直接得到该元素的地址,因为数组是用一段连续的内存地址来存储元素的,所以当你访问arr[n]时,计算机直接就可以得到它的地址:arr[0]的地址+间隔数据地址*n。时间复杂度为O(1)以上图为列:arr[n]的地址是1000+4*n
-
为什么插入删除低效??
当你在第k个位置插入元素时,你需要将k个元素之后的数都往后移动一位,再将第k个元素赋值为你要插入的元素。这里的时间复杂度为O(n),删除操作类似;
链表
链表相比于数组插入与删除操作较快,时间复杂度为O(1),但是它不支持随机访问,如果我们要访问第k个元素,我们需要从头开始遍历,我们来比较一下他与数组的关系
用代码来演示一下:
/**
*单向链表,next指向下一个节点
*/
function ListNode(val) {
this.val = val;
this.next = null;
}
/**
*双向链表,pre指向前一个节点
*/
function ListNode(val) {
this.val = val;
this.pre = null;
this.next = null;
}
/**
*循环链表,最后一个节点指向第一个节点
*/
function ListNode(val) {
this.val = val;
this.next = this;
}
/**
*循环双向链表,第一个接点pre指向最后一个节点,最后一个节点next指向第一个节点
*/
function ListNode(val) {
this.val = val;
this.pre = this;
this.next = this;
}
我们在用图来演示一下链表的插入与删除操作操作:
链表实战
给定数据格式如下:/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var addTwoNumbers = function(l1, l2) {
};
这是一道比较典型的大数相加的题目,也可以用数组来实现,具体分析可以看我链接中给出的分析。
队列
队列是以一种基于数组或链表的特殊数据结构,数组或者链表支持取出中间的某个数据,队列中你只能按照你存放的顺序依次取出,参考排队买口罩,先排队的先买。
- 基于数组的实现:
当我们存入数据时存到数组尾部,取数据时从数组头拿数据
(js的数组是动态的,天生支持这种操作)
- 基于链表的实现
栈
栈也是以一种基于数组或链表的特殊数据结构,栈是一种先存入的数据后消费的模型,如果你喝过泡腾片就知道我们把泡腾片装入盒子后,要想再取出来,是按照我们放入的相反顺序取出的
栈也是可以基于链表或者数组来实现,接下来我们来看看实际列子:
前端路由的导航实现就是依赖与这个数据模型,react-dom-router后者vue-router中提供了push,replace,go这写方法,push就是一个入栈的操作,replace是先出栈再入栈,go是不断的出栈知道目标页面为止。
浏览器的前进与后退也是基于这个数据模型,不同的是它需要两个栈来存储数据。
递归
递归是什么?如果你还记得高中的数学归纳法,这其实是类似的
递归有三个比较重要的基本步骤:
- 不断拆分出子问题。(递)
- 最终的子问题可以求解。(解决)
- 将求解后的子问题向上返回最终得到初始问题的解。(归)
递归与栈的关系
为什么我要在这里说递归呢? 它和我们的数据结构栈有着非常紧密的关系。
回到上面的三个步骤其实对应的就是下面的步骤:
- 入栈
- 开始出栈
- 出栈,直至栈空问题解决
递归多刷题才能找到感觉: 递归题目列表
基础数据结构二
二叉树
二叉树是一种非线性数据结构,每个节点最多只有两个子节点,看图:
其中2和3又叫满二叉树和完全二叉树
为什么我要提一下这两颗树?
我们先要来看看树的存储方式:
它和栈、队列一样可以用两种方式(数组或者链表来实现): (你可以把链表看成一颗特殊的树)
-
链式存储:
-
顺序存储
当树为一颗满二叉树和完全二叉树时我们可以用顺序存储的方式是最好的选择
二叉树的遍历方式
- 先序遍历:中左右
- 中序遍历:左中右
- 后序遍历:左右中
对应代码:
preOrder(root) {
if (root == null) return;
console.log(root);
preOrder(root.left);
preOrder(root.right);
}
inOrder(root) {
if (root == null) return;
preOrder(root.left);
console.log(root);
preOrder(root.right);
}
postOrder(root) {
if (root == null) return;
postOrder(root->left);
console.log(root);
postOrder(root->right);
}
二叉查找树(Binary Search Tree)
二叉查找树:在树中的任意一个节点,其左子树中的每个节点的值,都要小于这个节点的值,而右子树节点的值都大于这个节点的值
二叉查找树的查找过程:
可见其时间复杂度与树的深度相关,平均查找时间为O(log(n))
红黑树与平衡二叉查找树
如果在二叉查找树中,所有的节点都只有左节点那么查找的时间复杂度就会变为O(n),所以我们需要一种数据结构来保证其时间复杂度稳定在O(log(n)).
平衡二叉树: 二叉树中任意一个节点的左右子树的高度相差不能大于 1。
有了这样的数据结构那么我们就可以保证查找的时间复杂度基本维持在O(log(n))
那么为什么实际开发总能听到红黑树的影子呢?它又解决了什么问题?
在实际开发中,数据是变动的,当我们向数据中添加或者删除一天数据时,我们需要维持平衡二叉树的数据结构,频繁操作会导致时间复杂度退化,我们来思考一下引入平衡二叉树其目的是为了使查找的时间复杂度接近O(log(n)),那么我们只需要一颗尽可能平衡的树就可以了,它就是红黑树。
红黑树:
-
根节点是黑色的;
-
每个叶子节点都是黑色的空节点(NIL),也就是说,叶子节点不存储数据;
-
任何相邻的节点都不能同时为红色,也就是说,红色节点是被黑色节点隔开的;
-
每个节点,从该节点到达其可达叶子节点的所有路径,都包含相同数目的黑色节点;
红黑树中包含最多黑色节点的路径不会超过 log2n,加入红色节点之后,最长路径不会超过 2log2n,也就是说,红黑树的高度近似 2log2n。
红黑树的实现?很复杂你可以自行百度。
堆
先跳过这一个数据结构,到排序的时候再说
图 Graph(qq中的好友关系)
-
无向图:(当两个点之间有边,则建立好友关系)
-
有向图:(微博允许单向关注)
-
带权图:(亲密度)
图的存储
- 二维数组
- 邻接表(数组加链表)
图的搜索(深度和广度优先搜索)
- 广度优先搜索(Breadth-First-Search):
- 深度优先搜索(Breadth-First-Search):