时间复杂度&空间复杂度

Trade-off 权衡（空间时间的权衡，时间换空间，空间换时间）
如何分析一个算法的时间复杂度：
1、通过程序去运行
2、关注循环次数最多的那段代码

//时间复杂度为n
int n=10;
for(int i = 0; i <n; i++ ){
...
}
//时间复杂度n*2；2n，时间复杂度不考虑系数也就是n
int n=10;
for(int i = 0; i <n; i++ ){
  for(int j=0; j<2; j++){
...
  }
}
//若上段代码和下段代码在同一段程序代码内，可以关注上一段的时间复杂度，因为上一段的循环次数没有下段代码多，时间复杂度为n^2
for(int i = 0; i <n; i++ ){
  for(int j=0; j<n; j++){
...
  }
}

常见数据结构的时间复杂度
O(1) -> HashMap
O(logn) ->二叉树
O(n) -> for循环
O(nlogn) ->for循环嵌套二叉树
O(n^2) -> for循环嵌套for循环
...

空间复杂度（开辟空间的趋势）

//空间复杂度O(n)
int[]  m = new int[n];
for (int i =0; i < n; i++){
}
//空间复杂度为n^2
int[][] n = new int[n][n];
for (int i =0; i < n; i++){
}

常见的复杂度大小排序
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3)... < O(2^n) < O(n!)