一、代码效率优化方法论
熟练应用数据结构的知识，建立算法思维，完成代码效率的优化。
- 复杂度是衡量代码运行效率的重要度量因素
- 计算机通过一个个程序去执行计算任务，也就是对输入数据进行加工处理，并最终得到结果的过程；
- 每个程序都是由代码构成的，编写代码的核心就是要完成计算；
- 但对于同一个计算任务，不同计算方法得到结果的过程复杂程度是不一样的，这对实际的任务处理效率就有了非常大的影响；
- 在实际应用中需要讲究合理的计算方法，去通过尽可能低复杂程度的代码完成计算任务；
- 那提到降低复杂度，我们首先需要知道怎么衡量复杂度。
代码执行过程中会消耗计算时间和计算空间，那需要衡量的就是时间复杂度和空间复杂度。
不管是时间还是空间，它们的消耗程度都与输入的数据量高度相关，输入数据少时消耗自然就少。为了更客观地衡量消耗程度，我们通常会关注时间或者空间消耗量与输入数据量之间的关系。
复杂度是一个关于输入数据量 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)。
这段代码的开发，就是借鉴了方法论中的步骤三，通过采用更复杂、高效的数据结构，完成了时空转移，提高了空间复杂度，让时间复杂度再次降低。
降低复杂度，优化程序的核心的思路如下：
- 第一步，暴力解法。在没有任何时间、空间约束下，完成代码任务的开发。
- 第二步，处理无效操作。将代码中的无效计算、无效存储剔除，降低时间或空间复杂度。
- 第三步，时空转换。设计合理数据结构，完成时间复杂度向空间复杂度的转移，以空间换时间。
