时间复杂度和空间复杂度分析_二叉树操作时间性空间性分析

一、时间复杂度
1.最常见的时间复杂度（注意：只看最高复杂度的运算）
O(1)：常数复杂度；
O(log n):对数复杂度；——>for循环或者while循环中与n的乘阶有关
O(n)：线性时间复杂度；——>单循环
O(n^2)：平方；——>嵌套循环
O(n^3)：立方；
O(2^n)：指数；——>递归计算斐波拉契数列
O(n!)：阶乘；
2.递归时间复杂度分析(画出树的分析树)

每增加一层就要增加2^n次运算；
a.使用主定理来计算递归函数的时间复杂度
二分查找：O(logn)；
二叉树的遍历：O(n)：每个节点都需要访问一次；
排好序的二维矩阵中进行二分查找：O(n)
归并排序：O(nlogn)
3.常见面试题
a.二叉树遍历，前序、中序、后序的时间复杂度
都是O(n)
b.图的遍历的时间复杂度
O(n)——>将遍历树或者图中的每一个节点，并且每一个节点只访问一次；
c.搜索算法（DFS、BFS的时间复杂度是多少）
O(n)
二、空间复杂度
主要是看算法在运行过程中需要创建多少个与n变量相关的临时变量；