code前端网前端算法：时间、空间复杂度与数据结构栈和队列实现
1.做这个系列的理由和计划
前段时间遇到了一个实际问题，如何最优选币。数学描述如下： 求解线性方程问题：
1x + 5y +10z + 15k + 20*j = 16；我刚刚开始思考如何求解多元方程并转向矩阵解。结果我越研究它，它就变得越复杂。后来我发现这和背包问题很相似；然后复习了一些算法和数据结构的知识，这个系列就诞生了。我的计划是一一介绍相关的数据结构以及如何使用它们。一旦实现了JavaScript，然后是一些经典的应用程序和示例；废话不多说，先从最基本的开始：复杂度、栈、队列；
2. 复杂性
说到算法和数据结构，无非是解决两个问题两个问题： 1、如何更快、更准确地得到预期的结果； 2、如何用尽可能少的资源达到预期效果；这两个问题就是我们平时讲的性能问题，这两个问题都解决了。这解决了大多数性能问题；那么两者如何衡量或选择呢？有时您无法同时实现两者。如果不是为了占用更少的资源而放弃时间，那不就是牺牲一些资源存储来更快地得到预期的结果吗？这包括空间复杂度和时间复杂度
空间复杂度：这意味着为了实现某个功能或方法，我们需要占用我们的空间。在许多情况下，计算机内存资源可能不是优先考虑的问题。只要速度能够达到，例如sort中的counting sort就会定义一个中间数组。字段长度是要排序的字段的最大值。毫无疑问是的。需要更多内存；
时间复杂度：时间复杂度以大写O表示。虽然我们无法从代码中准确计算出执行时间，但也是不现实的，因为这个时间与操作系统和硬件有关，所以通常会有一个估计表达的价值；最喜欢的一点是看代码被重复执行了多少次 O(n)；
O(1):这种情况下，无论计数方法如何执行，++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)
}
}
}
数据结构：
1。堆垛机
堆垛机是一套遵循 FILO（先进后出）原则的有序装置。新添加的元素或要移除的元素都存储在栈的同一端，称为栈顶，另一端称为栈底。在堆栈中，新元素位于堆栈顶部附近，旧元素位于底部附近。
如何实现栈数据结构？
首先，我们定义一些栈API：
push(val): 向栈顶添加一个元素；
size(): 返回堆栈大小；
isEmpty():如果堆栈为空则返回
pop():出栈
clear(): : 返回顶部元素堆栈 操作简单： 您是否在想：堆栈的实际使用？ 在Vue中解析模板时，会使用栈来判断模板字符是否合法。这和很多编辑器在编写代码时检查我们编写的 HTML 元素是否关闭的原理是一样的。 队列是一组有序的项目，遵循先来先服务（FIFO，也称为先来先服务）策略。队列在末尾添加新元素并从顶部删除元素。最后添加的元素必须位于队列的末尾。事实上，队列最常见的例子就是队列。 如何实现队列数据结构？ 首先，我们定义一些队列API： enqueue(val)：向队列中添加一个元素； size(): 返回队列的大小； isEmpty()：返回队列是否为空。相当常见，像很多任务事件队列、vue更新队列、vue mixin合并队列，都是基于先进先出先出原则 思考：我们在做什么有没有更好的方法实现上面的队列和堆栈？上述实现有什么问题吗？ 双边队列是一种特殊的队列，它允许我们同时从前端和后端添加和删除元素。它基于基本前端定义的变体 API 接口： addFront(element)： 此方法将一个新元素添加到双边队列的前端。 addBack(element): 此方法向后端双端队列添加一个新元素。 removeFront(): 此方法从双端队列的前面删除第一个元素。 removeBack(): 此方法从后端双端队列中删除第一个元素。 peekFront(): 此方法返回双端队列开头的第一个元素。 peekBack(): 此方法返回后端双端队列的第一个元素。 代码实现： 简单控制： 使用双边队列： 检查回文； 检查一段英文是否不是回文。一般来说，比较简单的方法是转为数组，然后倒序转为字符串，看两者是否相等来判断是否是回文；例如： ababa 倒序后仍然是 ababa；这是一个回文。同样，我们也可以使用双队列来判断是否是回文。它不是回文；总体思路就是将一个字符串放入一个双端队列中，然后提取队列头和尾部看是否相等，直到队列列出的元素小于等于1个元素为止。代码实现如下： 思考：学习了队列和栈之后，如何利用队列和栈实现像cal('1+2-3+6/3')这样的四算术运算，结果是 16 想法： 1。对字符串 2 执行标签分析。创建标签栈，当碰到开始标签时将其插入栈中，当遇到结束标签 3 时将其弹出。匹配最后，检查托盘是否为空。如果为空，则表示已关闭。如果标签仍然存在，则说明该标签无法关闭。 我们使用了上面的堆栈和队列实现。数组用于向数组中删除和添加元素，数组操作实际上相当耗时。和其他静态语言一样，JavaScript 的数组操作其实很复杂，但是 js 引擎帮我们做了这些事情，比如从数组头删除或者添加一个元素，其他数组元素其实都得在内部进行翻译。例如，要向数组中插入一个元素，首先需要增加长度，然后将所有元素后移一个位置，使表头留空，然后放置要添加的元素。 ，所以最好使用对象而不是数组来实现 想法： 1。实现词法分析，分析词法队列：tokens； 2。获取标记 要处理，请定义一堆数字和一堆操作数 3。当您击中一个数字时，将该数字放入数字堆栈中。当他遇到操作员时，确定是否可以进行操作。如果该操作可以执行，则将从号码堆栈中删除。从栈中选择2个数字，然后将运算符从运算符栈中取出，然后执行相应的运算并将运算结果放入数栈中作为下一个操作数 1+2-3+6/3 =>标记 = [ '{类型：'数字'，值：'1'}， {类型：'运算符'，值：'+'}， '{类型：'数字' ,value:'2'}, {type: '运算符',value: '-'}, '{type: '数字',value:'3'}, {type: '运算符', value: '+'}, '{ type: 'number', value:'6'}, {type: 'operator', value: '/'}, '{type: 'number',value:'3'}, ]' 源码点击这里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
2。正面;
3。双边队列
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());//dimport {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思考与解答部分
确定标签是否已关闭
队列和堆栈的更好实现
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 = {};
}
}四种算术运算
相关源码实现地址
版权声明
本文仅代表作者观点，不代表Code前端网立场。
本文系作者Code前端网发表，如需转载，请注明页面地址。
