1.复杂度：如何衡量程序运行的效率？

1-1 复杂度是什么？

• 复杂度是衡量代码运行效率的重要的度量因素;
• 首先，这段代码消耗的资源是什么？(消耗计算时间和计算空间)
• 其次，这段代码对于资源的消耗是多少？
• 复杂度是一个关于输入数据量 n 的函数;
• 计算复杂度与具体的常系数无关;O(n) 与 O(2n) 表示一样的复杂度
• 多项式级的复杂度相加的时候，选择高者作为结果; O(n²) + O(n)与 O(n²) 表示一样的复杂度
• O(1) 也表示一个特殊的复杂度，与输入数量n无关
  

1-1-1 实例分析

下面看一个实例：输入数组a = [1,2,3,4,5],要求输出数组b,值为[5,4,3,2,1]

方法一：定义并初始化一个b数组，数组长度等于a数组，且每一个元素为0，通过for循环，从左到右将a数组从右向左赋值给b

• 初级做法

 function s1_1(){
  let a = [1,2,3,4,5];
  let b = Array(5).fill(0);
  for(let i = 0; i < a.length;i++){
    b[a.length - i - 1] = a[i]
  }
  return b;
 }

• 优化后

以上方法，时间复杂度与数组长度有关，为O(n)；空间复杂度，即重新定义了b数组，与a数组同等长度，为O(n)；
方法二：定义一个中间变量temp,然后取a的一半数据，交换位置，再将值return

 function s1_2(){
  let a = [1,2,3,4,5];
  let temp;
  for(let i = 0; i < a.length/2;i++){
    temp = a[i];
    a[i] = a[a.length - i - 1];
    a[a.length - i - 1] = temp;
  }
  return a;
 }

以上方法，时间复杂度为O(n/2)，也就是O(n)；
空间复杂度，需要一个temp变量，它与数组长度无关，不论数组多长，它都只需要一个temp变量，所以空间复杂度，为O(1)；

1-1-2 总结：

总结：对于同一个问题，采用不同编码方法，对时间和空间的损耗是有可能不一样的

1-2 时间复杂度与代码结构的关系

时间复杂度，与代码结构有非常强的关系

1-2-1 实例分析1：

下面看一个实例：定义一个数组a = [1,4,3],查找数组a中的最大值

 function s1_3(){
   let a = [1,4,3]
   let b = -1;
   for(let i = 0; i < a.length; i++){
     if(a[i] > b){
       b = a[i]
     }
   }
   return b;
 }

以上方法，时间复杂度，就是将数组遍历一遍，也就是O(n)；

1-2-2 实例分析2：

下面看再一个实例：定义一个数组a = [1,3,4,3,4,1,3],查找数组中出现次数最多的那个数组

 function s1_4(){
   let a = [1,3,4,3,4,1,3];
   let max_val = -1;
   let max_time = 0;
   let time_temp = 0;
   for(let i = 0;i < a.length;i++){
      time_temp = 0;
      for(let j = 0; j < a.length; j++){
        if(a[i] === a[j]){
          time_temp++
        };
      }
      if(time_temp > max_time){
        max_time = time_temp;
        max_val = a[i];
      }
   }
   return max_val
 }

这段代码中，使用了双循环，时间方面的消耗就是n*n,即时间复杂度O(ⁿ)；
由以上例子，我们可以做以下结论：

1-2-3 总结：

• 一个顺序结构的代码，复杂度为O(1)
• 二分查找，采用分而治之的二分策略，时间复杂度为O(logn)
• 一个简单的for循环，时间复杂度为O(n)
• 两个顺序执行的for循环，时间复杂度是O(n)+O(n)=O(2n)，其实也是 O(n)
• 两个嵌套的for循环，时间复杂度为O(n²)

1-3 降低时间复杂度的必要性

很有必要，不同的时间及空间复杂度，会直接影响到计算次数

1-4 总结

复杂度细分为时间复杂度和空间复杂度，其中时间复杂度与代码的结构设计高度相关；
空间复杂度与代码总数据结构的选择高度相关

• 1.复杂度它与具体常系数无关；O(n) 与 O(2n)表示一样的复杂度
• 2.复杂度相加时，选择高者作为结果；也就是说 O(n²)+O(n) 和 O(n²) 表示的是同样的复杂度
• 3.O(1) 也是表示一个特殊复杂度；即任务与算例个数 n 无关