《每日一学》2018年9月28 日

昨天在 Python 实战交流群里发起一个讨论:

在如下这个常见的遍历场景中,如何优化代码降低时间复杂度?

今天提供一下我的思路供大家参考:

上面的 example 中虽然表面上看是 2 层遍历,但其实是三层遍历, for _ in range(1000) 第一层,for item in ['apples', 'pears', 'bananas'] 第二层,item in vector 第三层,每一层的时间复杂度都为:O(n)

常规优化思路:

降低遍历层级——经过分析觉得无法优化

降低遍历次数——引入短路法

快速查找到元素——引入二分法查找

经过分析,第一层遍历与第二层遍历次数无法进行减少,第三层引入短路法来减少遍历次数,具体实施:观察需要打印的元素都以 s 结尾(总之要找到共同的特征),采用 and (其他语言为:&&) 判断表达式短路的方式减少遍历的次数,例如:

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180928G1TSRB00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券