数据结构与算法的常见时间复杂度和空间复杂度
一、时间复杂度
时间复杂度经常使用Big O notation来表示。 O表示某个时间复杂度是n的怎样的一个函数 O(1)：Constant Complexity 常数复杂度 。 O(log n)：Logarithmic Complexity 对数复杂度。 O(n)：Linear Complexity 线性时间复杂度。 O(n^2)：N square Complexity 平方。 O(n^3)：N cube Complexity 立方。 O(2^n)：Exponential Growth 指数。 O(n!)：Factorial 阶乘。
例子：计算1+2+3+…+n 方法一：从1到n循环累加 y = 0 for i = 1 to n y += i 时间复杂度为O(n)
方法二：使用求和公式 y = n * (n + 1) / 2 时间复杂度为O(1)
计算递归的时间复杂度 如上图 1、二分查找时间复杂度为O(logn) 2、二叉树遍历时间复杂度为O(n) 3、二维矩阵二分查找时间复杂度为O(n) 4、归并排序时间复杂度为O(nlogn)
例子： 1、二叉树遍历，前中后序时间复杂度是多少 都是O(n)，因为无论是前序中序还是后序，遍历二叉树时它的每个节点会访问一次且仅访问一次，所有他的时间复杂度是线性于二叉树的节点总数 2、图的遍历 与二叉树相同，他的每个节点也是访问一次且仅访问一次，时间复杂度线性于图的总节点数，也是O(n) 3、DFS深度优先搜索算法、BFS广度优先搜索算法 都是O(n)，n为搜索空间的节点总数
下一篇：
数据结构常见结构和算法时间复杂度