前端算法系列之一:时间复杂度、空间复杂度以及数据结构栈、队列的实现

JasonCloud 2021-01-23 10:26:07
前端 算法 系列 时间 法系


一、此系列的缘由和计划

前段时间遇到一个实际问题怎么最优取币的问题,数学描述就是如下多元一次方程求解问题:

1x + 5y +10z + 15k + 20*j = 16 ;刚开始想着如何求解多元方程,王矩阵求解去了,结果越做越复杂,后面发现这个和背包问题很像;然后就再重温一下一些算法和数据结构的知识,也就有了这个系列,我计划是把相关数据结构都一一介绍一遍,以及用JavaScript实现一遍,然后一些经典用于和实例;话不多说从最基本的开始:复杂度、栈、队列;

二、复杂度

说到算法和数据结构无非就是要解决两个问题:1、是如何更加快速准确的得到预期结果;2、如何占用尽可能少的资源来得到预期结果;而这两个问题也就是我们平时说到的性能问题,解决了这两个问题也就解决了大部分的性能问题;那怎么去衡量或者说去取舍这两者呢,有的时候这两者是不可兼得的,要不是为了占用少的资源而舍去时间的追求,要不就是为了更快速的达到预期结果而牺牲掉一定的资源存储,这里涉及到空间复杂度和时间复杂度

空间复杂度:这个就是指为实现某个功能或者方法要占用我们电脑的内存资源,对于很多情况下可能内存资源不是首要的,只要速度快能实现,比如排序中的计数排序它会要定义一个中间数组,数组的长度是要排序数组的最大值,这样无疑是需要更多的内存开销的;

时间复杂度:时间复杂度用大O来表示,虽然我们无法用从代码去准确的计算执行的时间,这也是不现实因为这个时间和操作系统、硬件都有关系,所以我们一般是有预估值来表示;通俗点就是看代码被重复执行的次数O(n);

O(1): 这种情况不论这么执行count方法,方法里面++n都只会执行一次,不会随着参数n的增加而变化,这种时间复杂度是一个常数;

function count (n) { return ++n; } count(n);

O(n): 这种情况就是随着参数的变化,代码被执行的次数呈现线性化的变化;

function consoleFn(n) {
for(let i = 0; i < n; i++){
console.log(i)
}
}

O(log2n):这种我们称为对数复杂程度;像二分法查找之类的;2^i = n => 得出 i = log2n;

function consoleFn(n) {
let i = 1;
while(i < n){
i = i * 2;
console.log(i);
}
}

O(nlog2n):线性对数;像快排的时间复杂度

function consoleFn(n) {
for(let j = 0; j < n; j++) {
let i = 1;
while(i < n){
i = i * 2;
console.log(i);
}
}
}

O(n2):这种情况就是执行次数会随着n的增加而出现倍数的增加;

function consoleFn(n) {
for(let i = 0; i < n; i++){
for(let j = 0; j < n; j++){
console.log(i)
}
}
}

微信图片_20210115153044.jpg

数据结构:

1、栈

栈是一种遵从先进后出(FILO)原则的有序集合。新添加或待删除的元素都保存在栈的同一端,称作栈顶,另一端就叫栈底。在栈里,新元素都靠近栈顶,旧元素都接近栈底。

2-1Q201204153P8.gif

怎么实现一个栈型数据结构呢?

首先我们先定一下栈他的一些api:

push(val):栈顶增加一个元素;

size():返回栈的大小;

isEmpty(): 返回栈是否是空

pop():出栈

clear(): 清空栈

peek(): 返回栈顶元素

export default class Stack {
constructor() {
this.items = [];
}
push(val) {
this.items.push(val);
}
size() {
return this.items.length;
}
isEmpty() {
return this.items.length === 0;
}
pop() {
return this.items.pop();
}
peek() {
return this.items[this.items.length - 1]
}
clear() {
this.items = [];
}
}

简单操作:

const stack = new Stack();
console.log(stack.isEmpty()); // true
stack.push(5);
stack.push(8);
stack.push(11);
stack.push(15);
console.log(stack.isEmpty()); // false
console.log(stack.size());// 4
console.log(stack.peek());//15
stack.pop();// 15
console.log(stack.size());// 3
console.log(stack.peek());//11

微信图片_20210117211447.jpg

思考:栈的实际应用?

vue中对模板进行解析的时候判断模板字符是否合法就运用了栈,这和很多编辑器在书写代码时候校验我们写的HTML元素是否闭合一样的原理。

2、队列;

队列是遵循先进先出(FIFO,也称为先来先服务)原则的一组有序的项。队列在尾部添加新元素,并从顶部移除元素。最新添加的元素必须排在队列的末尾。在现实中,最常见的队列的例子就是排队。

20190621181828227.png

怎么实现一个队列数据结构呢?

首先我们也先定一下队列他的一些api:

enqueue(val):队列增加一个元素;

size():返回队列的大小;

isEmpty(): 返回队列是否是空

dequeue():出队列

clear(): 清空队列

peek(): 返回队列的首位

export default class Queue {
constructor() {
this.items = [];
}
enqueue(val) {
this.items.push(val);
}
size() {
return this.items.length;
}
isEmpty() {
return this.items.length === 0;
}
dequeue() {
return this.items.shift();
}
peek() {
return this.items[0]
}
clear() {
this.items = [];
}
}

简单操作:

const queue = new Queue();
queue.enqueue('a');
queue.enqueue('b');
queue.enqueue('c');
queue.enqueue('d');
console.log(queue.isEmpty()); // true
console.log(queue.size());// 4
console.log(queue.peek());// a
console.log(queue.dequeue());;// a
console.log(queue.dequeue());;// b
console.log(queue.dequeue());;// c

20180906175230552.png

队列的应用比较常见,比如很多任务事件队列、vue的更新队列、vue的mixin合并队列,都是根据先进先被执行先出队的原则

思考:我们在上面实现队列和栈有没有更好的实现方式?上面实现有什么问题?

3、双端队列

双端队列是一种允许我们同时从前端和后端添加和移除元素的特殊队列。他是基于基础队列上的变种

image.png

api接口的定义:

addFront(element):该方法在双端队列前端添加新的元素。

addBack(element):该方法在双端队列后端添加新的元素。

removeFront():该方法会从双端队列前端移除第一个元素。

removeBack():该方法会从双端队列后端移除第一个元素。

peekFront():该方法返回双端队列前端的第一个元素。

peekBack():该方法返回双端队列后端的第一个元素。

代码实现:

import Queue from "./QueueArr";
export class Deque extends Queue{
constructor() {
super();
}
addFront(element){
this.items.unshift(element);
}
addBack(element) {
this.enqueue(element);
}
removeFront() {
return this.dequeue();
}
removeBack() {
return this.items.pop();
}
peekFront() {
return this.items[0];
}
peekBack() {
return this.items[this.items.length - 1];
}
}

简单操作:

const deque = new Deque();
deque.addFront('b');
deque.addBack('c');
deque.addFront('a');
deque.addBack('d');
console.log(deque.size()) // 4
console.log(deque.peekFront());;// a
console.log(deque.peekBack());// d
console.log(deque.removeFront());//a
console.log(deque.removeBack());//d

双端队列的应用:

检查回文;

检查一段英文是不是回文,一般比较简单的方法是将其转换成数组,然后倒序一下再转化成字符串看两者是否相同,来判断是否是回文;比如:ababa倒序过来还是ababa;这就是回文了,同样的我们也可以通过使用双端队列来实现判断是不是回文;大概思路就是将字符串放进一个双端队列,然后分别取出队头和队尾看是否相同,直到队列出列元素小于等于1个元素,代码实现如下:

import {Deque} from "./Deque";
export const palindromeChecked = (str) => {
if(!str){
return false;
}
const deque = new Deque();
const strs = str.toLowerCase().split('');
for (let i = 0; i < strs.length; i++) {
deque.addBack(strs[i]);
}
let start = '', end = '', isTrue = true;
while (deque.size() > 1 && isTrue) {
start = deque.removeFront();
end = deque.removeBack();
if (start != end) {
isTrue = false;
}
}
return isTrue
}
console.log(palindromeChecked('adfds'));// false
console.log(palindromeChecked('adada'));// true

思考:通过学习了队列和栈,如何运用队列和栈去实现一个四则运算,比如cal('1+2-3+6/3')得到结果是16

部分思考解答

判断标签是否闭合

思路:

1、对字符串进行标签解析

2、创建标签栈,遇到开始标签进行压入栈,遇不到闭合标签进行出栈操作

3、匹配到最后,判断栈是否为空,如果为空说明都闭合了,如果还有说明有标签未能闭合

队列和栈更好的实现

我们上面对栈和队列的实现都是运用了数组,对数组进行元素的删除和增加,而对数组的操作实际上比较消耗的,像其他静态语言一样,其实JavaScript对数组操作一样是很复杂的只是js引擎帮我们做了这些事情,例如从数组的头部删除或者增加一个元素,其实内部都要进行平移数组其他元素,比如插入一个元素数组要先把长度增加,然后所有元素后移一位空出头部再把要增加的元素放入,所以相比起来运用对象来实现会比数组更加的好

export default class Queue {
constructor() {
this.counter = 0;// 计数器计算队列大小
this.items = {}; // 队列存储
this.lowestCount = 0; // 队列头
}
// 返回队列首位
peek() {
return this.items[this.lowestCount];
}
enqueue(element) {
this.items[this.counter] = element;
this.counter++;
}
dequeue() {
if (this.isEmpty()) {
return undefined;
}
const result = this.items[this.lowestCount];
delete this.items[this.lowestCount];
this.lowestCount++;
return result;
}
isEmpty() {
return this.size() === 0;
}
size() {
return this.counter - this.lowestCount;
}
clear() {
this.counter = 0;
this.lowestCount = 0;
this.items = {};
}
}

四则运算

思路:

1、实现词法分析解析出一个词法队列:tokens;

2、拿到tokens进行处理,这时候定义一个数字栈,一个操作数栈

3、当遇到数字时候将数字压入数字栈,遇到操作符时候,判断能否执行运算,能运算就从数字栈中出栈2个数,然后操作符栈出栈一个操作符,然后做相应的操作运算,并把运算结果压入数字栈,作为下一次的运算数

1+2-3+6/3 => tokens = [

'{type: 'number',value:'1'},

{type: 'operator', value: '+'},

'{type: 'number',value:'2'},

{type: 'operator', value: '-'},

'{type: 'number',value:'3'},

{type: 'operator', value: '+'},

'{type: 'number',value:'6'},

{type: 'operator', value: '/'},

'{type: 'number',value:'3'},

]'

未命名绘图.png

版权声明
本文为[JasonCloud]所创,转载请带上原文链接,感谢
https://segmentfault.com/a/1190000039067397

  1. 【计算机网络 12(1),尚学堂马士兵Java视频教程
  2. 【程序猿历程,史上最全的Java面试题集锦在这里
  3. 【程序猿历程(1),Javaweb视频教程百度云
  4. Notes on MySQL 45 lectures (1-7)
  5. [computer network 12 (1), Shang Xuetang Ma soldier java video tutorial
  6. The most complete collection of Java interview questions in history is here
  7. [process of program ape (1), JavaWeb video tutorial, baidu cloud
  8. Notes on MySQL 45 lectures (1-7)
  9. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  10. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  11. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  12. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  13. 【递归,Java传智播客笔记
  14. [recursion, Java intelligence podcast notes
  15. [adhere to painting for 386 days] the beginning of spring of 24 solar terms
  16. K8S系列第八篇(Service、EndPoints以及高可用kubeadm部署)
  17. K8s Series Part 8 (service, endpoints and high availability kubeadm deployment)
  18. 【重识 HTML (3),350道Java面试真题分享
  19. 【重识 HTML (2),Java并发编程必会的多线程你竟然还不会
  20. 【重识 HTML (1),二本Java小菜鸟4面字节跳动被秒成渣渣
  21. [re recognize HTML (3) and share 350 real Java interview questions
  22. [re recognize HTML (2). Multithreading is a must for Java Concurrent Programming. How dare you not
  23. [re recognize HTML (1), two Java rookies' 4-sided bytes beat and become slag in seconds
  24. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  25. RPC 1: how to develop RPC framework from scratch
  26. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  27. RPC 1: how to develop RPC framework from scratch
  28. 一次性捋清楚吧,对乱糟糟的,Spring事务扩展机制
  29. 一文彻底弄懂如何选择抽象类还是接口,连续四年百度Java岗必问面试题
  30. Redis常用命令
  31. 一双拖鞋引发的血案,狂神说Java系列笔记
  32. 一、mysql基础安装
  33. 一位程序员的独白:尽管我一生坎坷,Java框架面试基础
  34. Clear it all at once. For the messy, spring transaction extension mechanism
  35. A thorough understanding of how to choose abstract classes or interfaces, baidu Java post must ask interview questions for four consecutive years
  36. Redis common commands
  37. A pair of slippers triggered the murder, crazy God said java series notes
  38. 1、 MySQL basic installation
  39. Monologue of a programmer: despite my ups and downs in my life, Java framework is the foundation of interview
  40. 【大厂面试】三面三问Spring循环依赖,请一定要把这篇看完(建议收藏)
  41. 一线互联网企业中,springboot入门项目
  42. 一篇文带你入门SSM框架Spring开发,帮你快速拿Offer
  43. 【面试资料】Java全集、微服务、大数据、数据结构与算法、机器学习知识最全总结,283页pdf
  44. 【leetcode刷题】24.数组中重复的数字——Java版
  45. 【leetcode刷题】23.对称二叉树——Java版
  46. 【leetcode刷题】22.二叉树的中序遍历——Java版
  47. 【leetcode刷题】21.三数之和——Java版
  48. 【leetcode刷题】20.最长回文子串——Java版
  49. 【leetcode刷题】19.回文链表——Java版
  50. 【leetcode刷题】18.反转链表——Java版
  51. 【leetcode刷题】17.相交链表——Java&python版
  52. 【leetcode刷题】16.环形链表——Java版
  53. 【leetcode刷题】15.汉明距离——Java版
  54. 【leetcode刷题】14.找到所有数组中消失的数字——Java版
  55. 【leetcode刷题】13.比特位计数——Java版
  56. oracle控制用户权限命令
  57. 三年Java开发,继阿里,鲁班二期Java架构师
  58. Oracle必须要启动的服务
  59. 万字长文!深入剖析HashMap,Java基础笔试题大全带答案
  60. 一问Kafka就心慌?我却凭着这份,图灵学院vip课程百度云