在合并区间算法中，我们首先对区间进行排序，即O(logn(，然后对它们进行迭代以执行合并，即0(n(。
我看到它指出，这使得合并间隔算法O(n log n(。但据我所见，由于我们只执行一次排序，然后在间隔上迭代一次，因此我们的复杂性应该为O(logn(+O(n(=O(n。
那么我错过了什么？为什么在计算复杂性时，O(logn(和O(n(相乘而不是相加？
def merge(intervals):
if len(intervals) < 2:
return intervals
intervals.sort(key=lambda x: x.start)
mergedIntervals = []
start = intervals[0].start
end = intervals[0].end
for i in range(1, len(intervals)):
interval = intervals[i]
if interval.start <= end:
end = max(interval.end, end)
else:
mergedIntervals.append(Interval(start, end))
start = interval.start
end = interval.end
# add the last interval
mergedIntervals.append(Interval(start, end))
return mergedIntervals
错误是您认为排序是O(log n)。排序通常在O(n log n)或更糟的情况下实现(请参阅此处(。
其余的计算是正确的：O(nlog n) + O(n) = O(n log n)。