如何优化关联记录存在性校验算法，将复杂度从O(n²)降至O(log n)？

结论 #

不存在将该算法时间复杂度优化到O(log n)的可能，核心原因如下：

• 你需要校验至少n*(n-1)/2个元素对才能完整得到所有两两关联关系，这一步的操作量本身和n²呈正相关，没有预计算的索引或特殊前置条件的前提下，不可能做到对数级复杂度
• 单次校验函数funcCheckRecordsExists的调用次数不可能脱离元素对的总量级，本质上无法跳过必要的校验步骤

可落地的优化方案 #

你可以基于关联的对称性，把双层循环的校验次数砍掉一半，时间复杂度仍为O(n²)，但实际运行耗时会减少约50%，优化后的代码逻辑如下：

l1 = [A,B,C,D]
n = len(l1)
# 仅遍历i < j的元素对，避免重复校验(A,B)和(B,A)
for i in range(n):
    item1 = l1[i]
    for j in range(i+1, n):
        item2 = l1[j]
        is_exist = funcCheckRecordsExists(item1, item2)
        # 后续关联判定、元素移除逻辑可直接复用原有规则

额外优化思路 #

如果你的业务场景满足以下前置条件，可以进一步降低实际运行耗时：

• 若funcCheckRecordsExists支持批量查询，可以将所有待校验的元素对打包成一次请求调用，减少IO开销
• 若存在历史校验结果缓存，可以直接取缓存结果跳过重复校验，缓存命中率足够高的场景下可以大幅降低实际运行耗时

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