算法时间复杂度和空间复杂度——大O表示
时间复杂度
| 表示 | O(1) | O(log n) | O(n) | O(n^2) | O(2^n) | O(n!) |
|---|---|---|---|---|---|---|
| 时间 | 常数 | 对数 | 线性 | 幂次 | 指数 | 阶乘 |
| 例子 | 二分查找/简单递归 | 简单查找 | 选择排序 | 旅行商问题 |
算法运行时间是从其增速的角度度量的,
大O表示法是最糟糕情况下的运行时间。
常见O(n)例子：
1. 二叉树-前序、中序、后序（n为节点总数 ，每个节点访问一次且仅访问一次） 2. 图的遍历（n为图节点的总数，每个节点访问一次且金访问一次） 3. 搜索算法（n为搜索中节点总数）： 深度优先算法 DFS（depth first search） 广度优先算法 BFS（breadth first search）空间复杂度
空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。
一般来说，考虑额外辅助空间的大小
同时使用数组和递归时，深度取二者更长的。