一、代码效率优化方法论

熟练应用数据结构的知识，建立算法思维，完成代码效率的优化。

• 复杂度是衡量代码运行效率的重要度量因素
• 
  
• 计算机通过一个个程序去执行计算任务，也就是对输入数据进行加工处理，并最终得到结果的过程；
• 每个程序都是由代码构成的，编写代码的核心就是要完成计算；
• 但对于同一个计算任务，不同计算方法得到结果的过程复杂程度是不一样的，这对实际的任务处理效率就有了非常大的影响；
• 在实际应用中需要讲究合理的计算方法，去通过尽可能低复杂程度的代码完成计算任务；
• 那提到降低复杂度，我们首先需要知道怎么衡量复杂度。

代码执行过程中会消耗计算时间和计算空间，那需要衡量的就是时间复杂度和空间复杂度。

不管是时间还是空间，它们的消耗程度都与输入的数据量高度相关，输入数据少时消耗自然就少。为了更客观地衡量消耗程度，我们通常会关注时间或者空间消耗量与输入数据量之间的关系。

复杂度是一个关于输入数据量 n 的函数。假设你的代码复杂度是 f(n)，那么就用个大写字母 O 和括号，把 f(n) 括起来就可以了，即 O(f(n))。例如，O(n) 表示的是，复杂度与计算实例的个数 n 线性相关；O(logn) 表示的是，复杂度与计算实例的个数 n 对数相关。

通常，复杂度的计算方法遵循以下几个原则：

• 复杂度与具体的常系数无关：例如 O(n) 和 O(2n) 表示的是同样的复杂度。我们详细分析下，O(2n) 等于 O(n+n)，也等于 O(n) + O(n)。也就是说，一段 O(n) 复杂度的代码只是先后执行两遍 O(n)，其复杂度是一致的。
• 多项式级的复杂度相加的时候，选择高者作为结果：例如 O(n²)+O(n) 和 O(n²) 表示的是同样的复杂度。具体分析一下就是，O(n²)+O(n) = O(n²+n)。随着 n 越来越大，二阶多项式的变化率是要比一阶多项式更大的。因此，只需要通过更大变化率的二阶多项式来表征复杂度即可。
• O(1) 表示一个特殊复杂度：含义为某个任务通过有限可数的资源即可完成。此处有限可数的具体意义是，与输入数据量 n 无关。

一些经验性的结论：

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

降低时间复杂度的必要性：

假设某个计算任务需要处理 10 万 条数据，你编写的代码：

• 如果是 O(n²) 的时间复杂度，那么计算的次数就大概是 100 亿次左右；
• 如果是 O(n)，那么计算的次数就是 10 万 次左右；
• 如果能写出高效算法，在 O(log n) 的复杂度下完成任务，那么计算的次数就是 17 次左右（log 100000 = 16.61，计算机通常是二分法，这里的对数可以以 2 为底去估计）

通常在小数据集上，时间复杂度的降低在绝对处理时间上没有太多体现。但在当今        的大数据环境下，时间复杂度的优化将会带来巨大的系统收益。而这是优秀工程师        必须具备的工程开发基本意识。

复杂度通常包括时间复杂度和空间复杂度，在具体计算复杂度时需要注意以下几点：

• 它与具体的常系数无关，O(n) 和 O(2n) 表示的是同样的复杂度；
• 复杂度相加的时候，选择高次项作为结果，也就是说 O(n²)+O(n) 和 O(n²) 表示的是同样的复杂度；
• O(1) 也是表示一个特殊复杂度，即任务与算例个数 n 无关；
• 时间复杂度与代码的结构设计高度相关；
• 空间复杂度与代码中数据结构的选择高度相关；

for (i=0; i<n; i++) {
for (j=0; j<n; j++) {
for (k=0; k<n; k++) {
        }
for (m=0; m<n; m++) {
        }
    }
}
时间复杂度为O(n^3)

二、将“昂贵”的时间复杂度转换成“廉价”的空间复杂度

代码效率优化就是要将可行解提高到更优解，最终目标是：要采用尽可能低的时间复杂度和空间复杂度，去完成一段代码的开发。

代码效率的瓶颈可能发生在时间或者空间两个方面。如果是缺少计算空间，花钱买服务器就可以了，这是个花钱就能解决的问题；相反，如果是缺少计算时间，只能投入宝贵的人生去跑程序。即使你有再多的钱、再多的服务器，也是毫无用处。相比于空间复杂度，时间复杂度的降低就显得更加重要了。因此，可以发现这样的结论：相对而言，空间是廉价的，而时间是昂贵的。

假定在不限制时间、也不限制空间的情况下，你可以完成某个任务的代码的开发。这就是通常我们所说的暴力解法，更是程序优化的起点。

例如，如果要在 100 以内的正整数中，找到同时满足以下两个条件的最小数字：

• 除 5 余 2
• 除 7 余 3

暴力的解法就是，从 1 开始到 100，每个数字都做一次判断。如果这个数字满足了上述两个条件，则返回结果。这是一种不计较任何时间复杂度或空间复杂度的、最直观的暴力解法。

当你有了最暴力的解法后，就需要用上一讲的方法评估当前暴力解法的复杂度了。如果复杂度比较低或者可以接受，那自然万事大吉。可如果暴力解法复杂度比较高的话，那就要考虑采用程序优化的方法去降低复杂度了。

为了降低复杂度，一个直观的思路是：梳理程序，看其流程中是否有无效的计算或者无效的存储。

我们需要从时间复杂度和空间复杂度两个维度来考虑。常用的降低时间复杂度的方法有递归、二分法、排序算法、动态规划等；而降低空间复杂度的方法，就要围绕数据结构做文章了。

降低空间复杂度的核心思路就是：能用低复杂度的数据结构能解决问题，就千万不要用高复杂度的数据结构。

在程序开发中，连接时间和空间的桥梁就是数据结构。对于一个开发任务，如果你能找到一种高效的数据组织方式，采用合理的数据结构的话，那就可以实现时间复杂度的再次降低。同样的，这通常会增加数据的存储量，也就是增加了空间复杂度。

程序优化的核心的思路如下：

• 第一步，暴力解法。在没有任何时间、空间约束下，完成代码任务的开发。
• 第二步，处理无效操作。将代码中的无效计算、无效存储剔除，降低时间或空间复杂度。
• 第三步，时空转换。设计合理数据结构，完成时间复杂度向空间复杂度的转移，以空间换时间。

举例如下：

假设有任意多张面额为2元、3元、7元的货币，现要用它们凑出100元，求总共有多少种可能性。

count=0foriinrange(0, 100//7+1):
forjinrange(0, 100//3+1):
forkinrange(0, 100//2+1):
ifi*7+j*3+k*2==100:
count+=1print(f'总共有 {count} 种可能性')
运行结果如下：总共有134种可能性

在这段代码中，使用了 3 层的 for 循环。从结构上来看，很显然是 O( n³ ) 的时间复杂度。然而，仔细观察就会发现，代码中最内层的 for 循环是多余的。因为，当你确定了要用 i 张 7 元和 j 张 3 元时，只需要判断用有限个 2 元能否凑出 100 - 7* i - 3* j 元即可，代码改写如下：

count=0foriinrange(0, 100//7+1):
forjinrange(0, 100//3+1):
if (100-7*i-3*j) >=0and (100-i*7-j*3) %2==0:
count+=1print(f'总共有 {count} 种可能性')
运行结果如下：总共有134种可能性

经过优化后，代码的结构由 3 层 for 循环，变成了 2 层 for 循环。很显然，时间复杂度就变成了O(n²) 。这样的代码改造，就是利用了方法论中的步骤二，将代码中的无效计算、无效存储剔除，降低时间或空间复杂度。

查找出一个数组中，出现次数最多的那个元素的数值。例如，输入a= [1,2,3,4,6,5,6,6 ] 中，查找出现次数最多的数值。从数组中可以看出，只有6出现了3次，其余都是1次。显然6出现的次数最多，结果输出6。

a= [1, 2, 3, 4, 6, 5, 6, 6]
val_max, time_max=-1, 0foriinrange(0, len(a)):
time_tmp=0forjinrange(0, len(a)):
ifa[i] ==a[j]:
time_tmp+=1# 出现次数大于之前最大的   重新复制 value 和出现次数iftime_tmp>time_max:
time_max=time_tmpval_max=a[i]
print(val_max, time_tmp)     
运行结果如下：63

采用两层的 for 循环完成计算， 很显然时间复杂度是 O(n²)。第一层循环，对数组每个元素遍历。第二层循环，则是对第一层遍历的数字，去遍历计算其出现的次数。这样，全局再同时缓存一个出现次数最多的元素及其次数就可以实现。代码中，几乎没有冗余的无效计算。如果还需要再去优化，就要考虑采用一些数据结构方面的手段，来把时间复杂度转移到空间复杂度了。

这个问题能否通过一次 for 循环就找到答案呢？一个直观的想法是，一次循环的过程中，我们同步记录下每个元素出现的次数。最后，再通过查找次数最大的元素，就得到了结果。

具体而言，定义一个 k-v 结构的字典，用来存放元素-出现次数的 k-v 关系。那么首先通过一次循环，将数组转变为元素-出现次数的一个字典。接下来，再去遍历一遍这个字典，找到出现次数最多的那个元素，就能找到最后的结果了。

a= [1, 2, 3, 4, 6, 5, 6, 6]
d= {}
foriina:
ifiind.keys():
d[i] +=1else:
d[i] =1print(d)
fork, vind.items():
ifv>temp_max:
time_max=vprint(temp_max)
val_max=kprint(val_max, time_max)
运行结果如下：63

来计算下这种方法的时空复杂度。代码结构上，有两个 for 循环。不过，这两个循环不是嵌套关系，而是顺序执行关系。其中，第一个循环实现了数组转字典的过程，也就是 O(n) 的复杂度。第二个循环再次遍历字典找到出现次数最多的那个元素，也是一个 O(n) 的时间复杂度。

因此，总体的时间复杂度为 O(n) + O(n)，就是 O(2n)，根据复杂度与具体的常系数无关的原则，也就是O(n) 的复杂度。空间方面，由于定义了 k-v 字典，其字典元素的个数取决于输入数组元素的个数。因此，空间复杂度增加为 O(n)。

这段代码的开发，就是借鉴了方法论中的步骤三，通过采用更复杂、高效的数据结构，完成了时空转移，提高了空间复杂度，让时间复杂度再次降低。

降低复杂度，优化程序的核心的思路如下：

• 第一步，暴力解法。在没有任何时间、空间约束下，完成代码任务的开发。
• 第二步，处理无效操作。将代码中的无效计算、无效存储剔除，降低时间或空间复杂度。
• 第三步，时空转换。设计合理数据结构，完成时间复杂度向空间复杂度的转移，以空间换时间。