8月阅读周·秒懂算法:用常识解读数据结构与算法:日常代码中的大O
背景
去年下半年,我在微信书架里加入了许多技术书籍,各种类别的都有,断断续续的读了一部分。
没有计划的阅读,收效甚微。
新年伊始,我准备尝试一下其他方式,比如阅读周。每月抽出1~2个非连续周,完整阅读一本书籍。
这个“玩法”虽然常见且板正,但是有效,已经坚持阅读七个月。
已读完书籍:《架构简洁之道》、《深入浅出的Node.js》、《你不知道的JavaScript(上卷)》、《你不知道的JavaScript(中卷)》、《你不知道的JavaScript(下卷)》、《数据结构与算法JavaScript描述》、《WebKit技术内幕》、《前端架构:从入门到微前端》。
当前阅读周书籍:《秒懂算法:用常识解读数据结构与算法》。
日常代码中的大O
确定代码效率是优化的第一步。如果连代码运行速度都不知道,那又怎么知道所做的修改能不能让它更快呢?
此外,一旦确定了代码的时间复杂度,就能判断它是否需要优化。例如,一般认为复杂度为O(N2)的算法是比较“慢”的。所以,如果你判断自己的算法也属于此类,那么就应该停下来考虑有没有优化的方法。
当然,O(N2)的算法对于特定问题可能是最优解。但知道自己的算法不够快,则会让我们深入思考和分析,并寻找更好的方案。
偶数平均数
下面这个Ruby方法会读取一个数字数组,并返回其中所有偶数的平均数。如何用大O记法表示其效率呢?
def average_of_even_numbers(array)
# 因为我们定义偶数平均数为数组中偶数之和与偶数个数的商,所以需要同时记录偶数的和以及个数:
sum = 0.0
count_of_even_numbers = 0
# 遍历数组中的每个数,如果发现偶数,就更新和以及个数:
array.each do |number|
if number.even?
sum += number
count_of_even_numbers += 1
end
end
# 返回平均数:
return sum / count_of_even_numbers
end
大O分析法的根本在于回答如下核心问题:如果有N个数据元素,那么算法需要多少步?因此,首要任务是确定“N”个数据元素是什么。
本例中,算法处理的是传入的数字数组。那么“N”个数据元素指的就是这些数,其中N表示数组大小。
可以看出,该算法的核心是一个遍历数组中每一个数的循环,因此我们首先来分析这一循环。因为循环需要遍历N个元素,所以该算法需要至少N步。
进一步观察循环内部会发现在每轮循环中执行的步数不同。对于数组中的每一个数,都要检查它是不是偶数。如果是,则还需要额外两步:更新变量sum和count_of_even_numbers。因此,处理偶数比处理奇数要多执行两步。
大O分析法主要关注最坏情况。本例的最坏情况是,所有数都是偶数,那么每一轮循环都需要3步。因此,可以说该算法需要用3N步来处理N个数据元素。换言之,对于这N个数中的每一个,算法都要执行3步。
这一方法在循环之外还有一些步骤要执行。在进入循环之前,要初始化两个变量并将它们赋值为0。严格意义上讲,这需要2步。在退出循环之后还有1步:计算sum/count_of_even_numbers。也就是说,我们的算法在3N步之外还需要额外的3步,因此总的步数是3N + 3。
大O记法会忽略常数,因此简单地说,这是一个O(N)算法,而不是O(3N + 3)算法。
构词程序
下一个例子中的算法会读取一个单字母数组,并返回使用这些字母且长度为2的所有字符串组合。如果输入数组["a", "b", "c", "d"],那么程序会返回包含如下字符串组合的新数组。
[
'ab', 'ac', 'ad', 'ba', 'bc', 'bd',
'ca', 'cb', 'cd', 'da', 'db', 'dc'
]
下面是该算法的JavaScript实现。来看看能否给出它的时间复杂度:
function wordBuilder(array) {
let collection = [];
for(let i = 0; i < array.length; i++) {
for(let j = 0; j < array.length; j++) {
if (i !== j) {
collection.push(array[i] + array[j]);
}
}
}
return collection;
}
在循环中嵌套了另一个循环。外层循环会遍历数组中的每一个字母,记录其索引i。对于每一个索引i,我们都执行一个内层循环。内层循环会使用索引j再次遍历同一数组,只要i和j不相等,就把索引为i和j的字母连接起来。
要判断该算法的效率,还是需要先确定N个数据元素是什么。N都是传给函数的数组中元素的数量。下一步就是判断算法处理N个数据元素所需要的步数。在本例中,外层循环会遍历N个元素。对于每一个元素,内层循环都要再次遍历N个元素,也就是在N步的基础上再乘以N步。
就和一般的循环嵌套算法一样,它也是典型的O(N^2)算法。
数组抽样
从数组中抽取小块样本。因为输入数组预期会很大,所以只取数组的第一个、最中间的那个以及最后一个值。
函数的Python实现如下所示,来看看它的时间复杂度:
def sample(array):
first = array[0]
middle = array[int(len(array) / 2)]
last = array[-1]
return [first, middle, last]
主要数据是传入函数的数组,因此N表示数组中元素的数量。不过,无论N是多少,这个函数所需步骤数都相同。无论数组大小是多少,从数组的开头、中间和结尾读取都只需要1步。计算数组长度以及长度除以2同样只需要1步。
无论N是多少,步骤数都是固定的,因此这个算法是O(1)算法。
总结
学会了分析各种算法的时间复杂度,运用这些知识,可以帮助开发者系统地优化代码速度了。
作者介绍
非职业「传道授业解惑」的开发者叶一一。
《趣学前端》、《CSS畅想》等系列作者。华夏美食、国漫、古风重度爱好者,刑侦、无限流小说初级玩家。
如果看完文章有所收获,欢迎点赞👍 | 收藏⭐️ | 留言📝。
- 点赞
- 收藏
- 关注作者
评论(0)