昨天在 Python 实战交流群里发起一个讨论:
在如下这个常见的遍历场景中,如何优化代码降低时间复杂度?
今天提供一下我的思路供大家参考:
上面的 example 中虽然表面上看是 2 层遍历,但其实是三层遍历, for _ in range(1000) 第一层,for item in ['apples', 'pears', 'bananas'] 第二层,item in vector 第三层,每一层的时间复杂度都为:O(n)
常规优化思路:
降低遍历层级——经过分析觉得无法优化
降低遍历次数——引入短路法
快速查找到元素——引入二分法查找
经过分析,第一层遍历与第二层遍历次数无法进行减少,第三层引入短路法来减少遍历次数,具体实施:观察需要打印的元素都以 s 结尾(总之要找到共同的特征),采用 and (其他语言为:&&) 判断表达式短路的方式减少遍历的次数,例如:
领取专属 10元无门槛券
私享最新 技术干货