尝试实现O(nlgn)区间重叠索引对算法，却比O(n²)版本慢，求排查

需求是找出数组中存在重叠区间的索引对（输出时索引需+1）。举个例子：
输入 A=[[1,3],[4,5],[2,5],[4,6]]，需要返回 [(1,3),(2,4),(2,3),(3,4)]。

我尝试用分治思路实现时间复杂度O(nlgn)的Python算法，但实际运行速度反而比自己写的O(n²)版本更慢，搞不懂问题出在哪，附上我的代码：

def Helper(friends,array,p,q,r):#merge sort algorithm implementation 
    L = array[p:q+1]
    R = array[q+1:r+1]
    idx1 = p
    idx2 = q+1
    i = 0
    j = 0
    #print("L = ",L)
    #print("R = ",R)
    while i < len(L) and j < len(R):
        if L[i][0] in range(R[j][0],R[j][1]+1) or L[i][1] in range(R[j][0],R[j][1]+1):
            if idx1+i+1 != idx2+j+1:
                myTupple = (idx1+i+1,idx2+j+1)
                if myTupple not in friends:
                    friends.append(myTupple)
        i = i +1
        if j >= len(R) and i < len(L):
            j = 0
            i = i + 1
        elif j < len(R) and i >= len(L):
            j = j + 1
            i = 0
def DivideAndConquer(friends,array,p,r):
        if p >= r:
            return
        q = (p+r)//2
        DivideAndConquer(friends,array, p , q)
        DivideAndConquer(friends,array, q+1, r)
        Helper(friends,array,p,q,r)
       # A = [[1,4],[2,5],[7,9],[9,10],[6,10]]

def friendsFaster(Input):
    friends = []
    DivideAndConquer(friends, Input,0, len(Input)-1)
    return friends

问题出在哪 #

你的分治代码跑不过O(n²)版本，核心原因有这几个：

1. 重叠判断效率极低
   你用L[i][0] in range(R[j][0],R[j][1]+1)来判断区间重叠，range在Python里是生成一个序列，当区间范围很大时，这个判断会变成遍历整个序列，完全是没必要的开销。其实判断两个区间[a1,a2]和[b1,b2]重叠，直接用a1 < b2 and b1 < a2就够了，这是O(1)的操作。
2. Helper函数的循环逻辑混乱
   里面的i和j重置逻辑会导致L和R的元素被反复比较，原本合并阶段应该是O(n)的操作，结果变成了O(n²)，整个分治的时间复杂度直接崩了，比原生的O(n²)还慢。
3. 去重开销太大
   每次添加索引对前都用myTupple not in friends检查，list的in操作是线性扫描，结果越多，这个检查越慢。
4. 分治没用到排序优化
   标准的分治找重叠区间，得先把区间按起始点排序，这样合并阶段才能线性遍历找出跨区间的重叠对。你的代码没排序，导致合并阶段做了大量无效比较。

改进后的分治实现 #

先给区间带上原始索引并排序，再用分治处理，保证O(nlgn)的复杂度：

def find_overlapping_pairs(arr):
    # 给每个区间加上原始索引（+1后是结果需要的索引）
    indexed_intervals = [(interval[0], interval[1], idx + 1) for idx, interval in enumerate(arr)]
    # 按区间起始点排序
    indexed_intervals.sort()
    # 用集合存结果，去重效率高
    result = set()

    def divide_conquer(left, right):
        if left >= right:
            return
        mid = (left + right) // 2
        # 递归处理左右子区间
        divide_conquer(left, mid)
        divide_conquer(mid + 1, right)
        
        # 合并阶段：找左半和右半的重叠对
        # 因为左右都按起始点排序，左区间起始<=右区间起始，只要左区间的end > 右区间的start就重叠
        i = left
        for j in range(mid + 1, right + 1):
            right_start, right_end, right_idx = indexed_intervals[j]
            # 遍历左半部分，找到所有和当前右区间重叠的左区间
            while i <= mid:
                left_start, left_end, left_idx = indexed_intervals[i]
                if left_end > right_start:
                    # 索引对按小的在前存，避免重复
                    pair = (min(left_idx, right_idx), max(left_idx, right_idx))
                    result.add(pair)
                    i += 1
                else:
                    # 左区间起始更小且不重叠，后面的左区间起始更大，也不会重叠，直接break
                    break

    divide_conquer(0, len(indexed_intervals) - 1)
    # 转成有序列表，和示例输出格式一致
    return sorted(result)

# 测试示例
A = [[1,3],[4,5],[2,5],[4,6]]
print(find_overlapping_pairs(A))  # 输出 [(1, 3), (2, 3), (2, 4), (3, 4)]

为什么这个版本更快 #

• 排序后利用有序性：左右区间都按起始点排序，合并阶段不用做全量比较，线性遍历就能找到所有跨区间的重叠对，保证分治的时间复杂度是O(nlgn)。
• 高效的重叠判断：直接用数值比较代替range遍历，O(1)搞定判断。
• 集合去重：set的添加和查询都是O(1)，避免了列表线性扫描的高额开销。
• 循环逻辑优化：合并阶段的i不需要每次重置，利用有序性只遍历一次左半部分，进一步减少了不必要的操作。

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