概述

数据结构和算法本身解决的是“快”和“省”的问题，即如何让代码运行的更快，如何让代码更省空间。所以执行效率是算法一个非常重要的考量指标。只要讲到数据结构和算法就离不开时间、空间复杂度分校。复杂读分析是算法学习的精髓，只有掌握它，才知道写出的代码是否可以又快又省的稳定运行。

大O复杂度表示法

算法的执行效率，就是算法代码的执行时间。但是如何再不运行代码的情况下，用“肉眼”得到一段代码的执行时间呢？

• 如下代码，估算这段代码的执行时间

int cal(int n){
   int sum = 0;
   int i = 1;
   for(; i <= n; ++i){
     sum = sum + i;
   }
   return sum;
}

• 分析

假设每行代码执行的时间都一样，为unit_time。在这个假设的基础之上，第2、3行代码分别需要1个unit_time的执行时间，第4、5行都运行了n遍，所以需要2n * unit_time的执行时间，所以这段代码的执行时间就是(2n + 2) * unit_time。可以看出来所有代码的执行时间T(n)与每行代码的执行次数成正比。

• 如下代码，估算这段代码的执行时间

 int cal(int n) {
   int sum = 0;
   int i = 1;
   int j = 1;
   for (; i <= n; ++i) {
     j = 1;
     for (; j <= n; ++j) {
       sum = sum +  i * j;
     }
   }
 }

• 分析

第2、3、4行代码，每行需要1个unit_time的执行时间，第5、6行需要执行n遍，需要2n * unit_time的执行时间，第7、8行代码执行了n²遍，所以需要2n² * unit_time,所以整段代码的执行时间T(n)=(2n² + 2n + 3) * unit_time。

但是通过这两段代码执行时间的推导过程，我们可以得到一个非常重要的规律，那就是，所有代码的执行时间 T(n) 与每行代码的执行次数 n成正比。

第一个例子中的T(n) = O(2n+2)，第二个例子中的 T(n) = O(2n2+2n+3)。这就是大O时间复杂度表示法。大O时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度简称时间复杂度

• ⚠️只关注循环执行次数最多的一段代码