复杂度

复杂度是什么？

复杂度是衡量代码运行效率的重要衡量因素。

复杂度包括两个方面的负责度：时间复杂度、空间复杂度。

大 O 表示法 （Big O）

• 一般用大 O 表示法来描述复杂度，它表示的是数据规模 n 对应的复杂度
• 忽略常数、系数、低阶
  • 9 >> O(1)
  • 2n + 3 >> O(n)
  • n^2 + 2n + 3 >> O(n^2)
  • 4n^3 + 3n^2 + 2n + 1 >> O(n^3)

• 对数阶一般省略底数,统称为 logn
• O(1) < o(logn) < O(n) < O(nlogn) < O(n^2) < O(n3)<O(2n)

注意： 大 O 表示法仅仅是一种粗略的分析模型，是一种估算，能帮助我们快速了解一个算法的执行效率。

对比图：

计算方法

单个数据规模

function static void test (int n){
  //执行次数： n  + n + 1 + n = 3n => O(n)
  for(int i = 0 ; i < n ; i ++){
    System.out.println('test');
  }
}

function static void test (int n){
  //执行次数： n * n = n^2 => O(n^2)
  for(int i = 0 ; i < n ; i ++){
    for (int j = 0 ; j < n ; j ++){
      System.out.println('test');
    }
  }
}

多个数据规模的情况

function static void test (int n,int k){
  //执行次数： n + k  => O(n + k)
  for(int i = 0 ; i < n ; i ++){
    System.out.println('test');
  }
  for(int i = 0 ; i < k ; i ++){
    System.out.println('test');
  }
}

对于多个数据规模的，不能省略。

总结

时间复杂度与代码的结构设计高度相关。

空间复杂度与代码中数据结构的选择高度相关