Python中如何合并split遍历与业务循环以优化时间复杂度

核心优化思路 #

• 跳过split()方法生成临时字符串数组的步骤，手动遍历输入的价格字符串，边拆分边转换为整数存入列表，整个拆分+类型转换仅需一次字符串遍历，符合你要求的单次遍历完成拆分的需求
• 针对多次查询场景，先对价格列表做升序排序，后续每次查询使用二分查找直接得到符合条件的元素数量，避免每次查询都全量遍历价格列表，大幅降低多次查询的时间开销

优化后代码 #

import bisect

# 单次遍历完成价格拆分+整数转换
price_input = input()
prices = []
current_buf = []
for c in price_input:
    if c == ' ':
        if current_buf:
            prices.append(int(''.join(current_buf)))
            current_buf.clear()
    else:
        current_buf.append(c)
# 补全处理末尾的最后一个价格
if current_buf:
    prices.append(int(''.join(current_buf)))

# 排序后支持二分查询
prices.sort()

days = int(input())
for _ in range(days):
    query_val = int(input())
    # bisect_right返回的索引值正好等于小于等于查询值的元素个数
    print(bisect.bisect_right(prices, query_val))

性能对比 #

原代码的时间复杂度为O(L + D*L)，其中L为价格数量，D为查询天数：包含拆分字符串的1次L遍历，以及每次查询都要做的1次L遍历。
优化后代码的时间复杂度为O(L + L*logL + D*logL)：仅需要1次字符串遍历完成拆分，排序开销为O(L*logL)，每次查询仅需O(logL)复杂度，当L和D数值较大时，性能提升十分显著。

如果你的查询次数极少（仅1次），可以去掉排序和二分逻辑，拆分完成后直接遍历一次价格列表统计结果即可，整体仍比原代码少一次拆分后转整数的遍历开销。

内容的提问来源于stack exchange，提问作者Shashank Chaudhary