参考:https://www.bilibili.com/video/BV14f4y1C7hg
宝藏up主!
1.时间复杂度

O(1)

O(n)
复杂度看最高的

O(n2)

如果只是两个并列的for循环,时间复杂度还是O(n),100个并列的for循环,也是O(n)
这里有继承,两个循环分摊一个任务

O(logn)
二分搜索
O(nlogn)
排序
优化的方法:从低-级的复杂度寻找灵感
- O(n)->O(logn)使用二分搜索
- O(nlogn) -> O(n)遇到需要排序的题,想想能否通过数组,set, map,heap解
- O(n2)-> O(nlogn)遇到嵌套循环,想想能不能通过排序+-个for循环解
2.空间复杂度
O(1)
创建单一的变量
int a=1;
let b=1;
有很多题的空间复杂度是O(1)
O(n)
- 定义一个长度为n的数组,一定是自己创建的
- 定义一个长度为n的set, map
- 用for循环生成一个长度为n的链表
O(n2)
- 二维数组
- 维数组每个元素存放一个长度为n的set或者map或者链表
Leetcode刷题预备基础知识(JavaScript版)
原文:https://www.cnblogs.com/My-Coding-Life/p/14804003.html