熟练应用数据结构的知识,建立算法思维,完成代码效率的优化。
复杂度是衡量代码运行效率的重要度量因素
那提到降低复杂度,我们首先需要知道怎么衡量复杂度。
代码执行过程中会消耗计算时间和计算空间,那需要衡量的就是时间复杂度和空间复杂度。
不管是时间还是空间,它们的消耗程度都与输入的数据量高度相关,输入数据少时消耗自然就少。为了更客观地衡量消耗程度,我们通常会关注时间或者空间消耗量与输入数据量之间的关系。
复杂度是一个关于输入数据量 n 的函数。假设你的代码复杂度是 f(n),那么就用个大写字母 O 和括号,把 f(n) 括起来就可以了,即 O(f(n))。例如,O(n) 表示的是,复杂度与计算实例的个数 n 线性相关;O(logn) 表示的是,复杂度与计算实例的个数 n 对数相关。
通常,复杂度的计算方法遵循以下几个原则:
一些经验性的结论:
降低时间复杂度的必要性:
假设某个计算任务需要处理 10 万 条数据,你编写的代码:
通常在小数据集上,时间复杂度的降低在绝对处理时间上没有太多体现。但在当今的大数据环境下,时间复杂度的优化将会带来巨大的系统收益。而这是优秀工程师必须具备的工程开发基本意识。
复杂度通常包括时间复杂度和空间复杂度,在具体计算复杂度时需要注意以下几点:
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 以内的正整数中,找到同时满足以下两个条件的最小数字:
暴力的解法就是,从 1 开始到 100,每个数字都做一次判断。如果这个数字满足了上述两个条件,则返回结果。这是一种不计较任何时间复杂度或空间复杂度的、最直观的暴力解法。
当你有了最暴力的解法后,就需要用上一讲的方法评估当前暴力解法的复杂度了。如果复杂度比较低或者可以接受,那自然万事大吉。可如果暴力解法复杂度比较高的话,那就要考虑采用程序优化的方法去降低复杂度了。
为了降低复杂度,一个直观的思路是:梳理程序,看其流程中是否有无效的计算或者无效的存储。
我们需要从时间复杂度和空间复杂度两个维度来考虑。常用的降低时间复杂度的方法有递归、二分法、排序算法、动态规划等;而降低空间复杂度的方法,就要围绕数据结构做文章了。
降低空间复杂度的核心思路就是:能用低复杂度的数据结构能解决问题,就千万不要用高复杂度的数据结构。
在程序开发中,连接时间和空间的桥梁就是数据结构。对于一个开发任务,如果你能找到一种高效的数据组织方式,采用合理的数据结构的话,那就可以实现时间复杂度的再次降低。同样的,这通常会增加数据的存储量,也就是增加了空间复杂度。
程序优化的核心的思路如下:
举例如下:
假设有任意多张面额为 2 元、3 元、7 元的货币,现要用它们凑出 100 元,求总共有多少种可能性。
count = 0
for i in range(0, 100 // 7 + 1):
for j in range(0, 100 // 3 + 1):
for k in range(0, 100 // 2 + 1):
if i * 7 + j * 3 + k * 2 == 100:
count += 1
print(f'总共有 {count} 种可能性')
运行结果如下:
总共有 134 种可能性
在这段代码中,使用了 3 层的 for 循环。从结构上来看,很显然是 O( n³ ) 的时间复杂度。然而,仔细观察就会发现,代码中最内层的 for 循环是多余的。因为,当你确定了要用 i 张 7 元和 j 张 3 元时,只需要判断用有限个 2 元能否凑出 100 - 7* i - 3* j 元即可,代码改写如下:
count = 0
for i in range(0, 100 // 7 + 1):
for j in range(0, 100 // 3 + 1):
if (100 - 7 * i - 3 * j) >= 0 and (100 - i * 7 - j * 3) % 2 == 0:
count += 1
print(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, 0
for i in range(0, len(a)):
time_tmp = 0
for j in range(0, len(a)):
if a[i] == a[j]:
time_tmp += 1
# 出现次数大于之前最大的 重新复制 value 和出现次数
if time_tmp > time_max:
time_max = time_tmp
val_max = a[i]
print(val_max, time_tmp)
运行结果如下:
6 3
采用两层的 for 循环完成计算, 很显然时间复杂度是 O(n²)。第一层循环,对数组每个元素遍历。第二层循环,则是对第一层遍历的数字,去遍历计算其出现的次数。这样,全局再同时缓存一个出现次数最多的元素及其次数就可以实现。代码中,几乎没有冗余的无效计算。如果还需要再去优化,就要考虑采用一些数据结构方面的手段,来把时间复杂度转移到空间复杂度了。
这个问题能否通过一次 for 循环就找到答案呢?一个直观的想法是,一次循环的过程中,我们同步记录下每个元素出现的次数。最后,再通过查找次数最大的元素,就得到了结果。
具体而言,定义一个 k-v 结构的字典,用来存放元素-出现次数的 k-v 关系。那么首先通过一次循环,将数组转变为元素-出现次数的一个字典。接下来,再去遍历一遍这个字典,找到出现次数最多的那个元素,就能找到最后的结果了。
a = [1, 2, 3, 4, 6, 5, 6, 6]
d = {}
for i in a:
if i in d.keys():
d[i] += 1
else:
d[i] = 1
print(d)
for k, v in d.items():
if v > temp_max:
time_max = v
print(temp_max)
val_max = k
print(val_max, time_max)
运行结果如下:
6 3
来计算下这种方法的时空复杂度。代码结构上,有两个 for 循环。不过,这两个循环不是嵌套关系,而是顺序执行关系。其中,第一个循环实现了数组转字典的过程,也就是 O(n) 的复杂度。第二个循环再次遍历字典找到出现次数最多的那个元素,也是一个 O(n) 的时间复杂度。
因此,总体的时间复杂度为 O(n) + O(n),就是 O(2n),根据复杂度与具体的常系数无关的原则,也就是O(n) 的复杂度。空间方面,由于定义了 k-v 字典,其字典元素的个数取决于输入数组元素的个数。因此,空间复杂度增加为 O(n)。
这段代码的开发,就是借鉴了方法论中的步骤三,通过采用更复杂、高效的数据结构,完成了时空转移,提高了空间复杂度,让时间复杂度再次降低。
降低复杂度,优化程序的核心的思路如下:
作者:叶庭云 CSDN:https://yetingyun.blog.csdn.net/