时间复杂度是什么？

  • 它是一个函数，用大O描述，比如O(1),O(n),O(log n) ….。
  • 定性描述该算法的时间。

O(1)

  1. let i = 0;
  2. i += 1;

O(n)

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

O(1) + O(n) = O(n)

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

O(n)*O(n) = O(n^2)

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

O(logN)

let i = 1;

while(i<n) {
  console.log(i)
  i *=2;
}

空间复杂度

  • 一个函数，用大O表示，比如：O(1)、O(n)、O(n^2)…
  • 算法在运行过程中临时占用存储空间大小的量度

O(1)：

let i = 0;
i += 1;

O(n):

const list = [];
for(let i=0; i < n; i+=1) {
    list.push(i)
}

O(n^2):
其实就是一个矩阵。

const matrix = [];
for(let i = 0; i<n; i+=1) {
    matrix.push([]);
  for(let j = 0; j<n; j+=1) {
      matrix[i].push(j);
  }
}

栈

  • 一个后进先出的数据结构。
  • javascript中没有栈，但可以使用数组Array实现栈的所有功能。

基础--时间/空间复杂度、栈 - 图1

const stack = [];
//入栈
stack.push(1);
stack.push(2);
//出栈
const item1 = stack.pop()
const item2 = stack.pop()

image.png
第一个按钮continue(继续)，运行到下一个断点处。
第二个按钮：一行一行执行代码
第三个按钮：进入一个函数执行代码
第四个按钮：跳出一个函数执行代码。
第五个按钮：重新调试
第六个按钮：退出调试。

什么场景使用栈？

  • 使用后进先出的场景。比如：十进制转二进制；判断字符串括号是否有效 ；函数调用堆栈 。。。

    十进制转二进制。

    image.png

  • 后出来的余数反而排在前面。

  • 把余数一次入栈，然后再出栈，就可以实现余数倒序输出。

有效的括号。

(((())))

()()()
  • 越靠后的左括号，对应的右括号越靠前。
  • 左括号入栈，右括号出栈，最后栈空了就是合法的。

解题：

  • 对于没有闭合的左括号而言，越靠后的左括号，对应的右括号越靠前。
  • 满足后进先出，考虑用栈。

leetCode 20:
合法的
步骤：

  1. 新建一个栈。
  2. 扫描字符串，遇到左括号入栈，遇到和栈顶括号类型匹配的右括号就出栈，类型不匹配直接判定为不合法。

  3. 最后栈空了就合法，否则不合法。 ```javascript var isValid = function(s) { if(s % 2 === 1) {return false}; const v = new Map([[“(“,”)”],[“{“,”}”],[“[“,”]”]]); const stack = [];

    for(let i = 0; i< s.length; i++) {

     const c = s[i];
 if(v.get(c)) {
     stack.push(c)
 }else {
     const top = stack[stack.length - 1];
     if(c === v.get(top)) {
         stack.pop();
     }else {
         return false;
     }
 }

    }

    return stack.length === 0;

};


<a name="4a332d1c"></a>
#### js中的函数调用堆栈
```javascript
function greeting() {
  // [1]
  sayHi()
  // [2]
}

function sayHi() {
    return "Hi"
}

greeting()

//[3]
  • 最后调用的函数，最先执行完。
  • JS解释器使用栈来控制函数的调用顺序。
const func1 = () => {
    func2()
};
const func2 = () => {
    func3()
};
const func3 = () => {};

func1()

总结

  • 栈是一个后进先出的数据结构。
  • JavaScript中没有栈，但可以用Array实现栈的所有功能。
  • 栈常用操作：push、pop、栈顶元素：stack[stack.length - 1]。