一、时间复杂度分析
1、由数据范围反推算法复杂度以及算法内容
文章来源：https://www.toymoban.com/news/detail-536077.html
2、如何分析代码复杂度
（1）看循环
-
- 一层循环为O(N)，两层循环为O(n^2)
-
- 不包含输入输出所必须的循环
-
- 若两个循环，不互相嵌套，分别为m与n，则为O(m+n)
（2）看递归
-
- 主定理，不适用太麻烦
-
- 例如快排与归并排序：
一共logn层，每一层是O(N)的时间复杂度，则总复杂度为O(nlogn)
- 例如快排与归并排序：
（3）一些看似为O(n^2)，但实际为O(n)
-
- 即内层循环执行肯定 <=n
-
- 例如：
- 例如：
（4）数据结构
-
- 单链表： 插入一个数，删除列表头都是O（1）
-
- 栈与队列： 每次操作都是O（1）
-
- 单调栈与单调队列： 有点类似双指针，都是O（n），KMP内层也是 <=n，故为O（n）
-
- 并查集： 未加路径压缩为O（n），路径压缩为O（nlogn）
-
- 若并查集使用 1）路径压缩 2）按秩合并——则可以将复杂度降到O（loglogn）
-
- 堆： 完全二叉树，高度为logn，则删除与添加操作为O（logn）
-
- 哈希表： 增删改查近似为O（1）
（5）搜索问题
-
- 算一下执行多少次就可以了
-
- 例如：全排列：O（n * n!）
-
- 图的 dfs 与 bfs
-
- 保证每个点只被遍历一次
-
- 遍历每个点的边 =》即遍历所有边 m，O（n+m）
-
- log2（10^x）≈ 3x
（6）数学知识
- 埃氏筛法— O（nlogn）
-
- 质数的倒数和：loglogn
-
- 自然数的和：logn
（7）动态规划
- 计算量 = 状态数量 * 状态转移的计算量
（8）贪心
- 一般是 排序+循环 ，O（nlogn）
二、空间复杂度
文章来源地址https://www.toymoban.com/news/detail-536077.html
到了这里，关于四十五、时间/空间复杂度分析的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
