给定一组间隔，为什么计算pred[i]θ(N logn)的平均情况是？
给定一组间隔，为什么计算pred[i]θ(N logn)的平均情况是？
提问于 2013-06-01 13:28:05
所以我在看我的笔记，我真的不明白这部分：
定义f，s为间隔的开始和结束时间。按完成时间对所有间隔进行排序。因此，假设我们有一组间隔I_1，...，I_n，并且定义predi =最大的索引j，使得f_j _ <= _ s_i。(因此本质上i之前的下一个最接近的间隔不与i重叠)。
现在我们想要解决n中所有I_i的所有predi。为什么这个θ(N log n)的运行时间是？我认为，在最坏的情况下，所有的I_1，...，I_(i-1)都与I_i重叠；因此需要n-1个比较，然后n-2个比较，依此类推。最好的情况是没有一个间隔重叠，并且pred(i)对每个间隔进行1次比较。我不确定为什么“排序和计算predi值”的运行时是theta(n logn)。
回答 1
Stack Overflow用户
发布于 2013-06-01 13:58:00
您命名的条件max j使得fj < si不是重叠检查。相反，它是在间隔i结束之前开始的最后一个间隔(它们实际上可能重叠，也可能不重叠)。我认为您可以按开始时间(即theta(nlogn) )对间隔进行排序，然后使用二进制搜索来查找每个si的fj
附注:θ我指的是平均情况，不是你提到的最坏的情况。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/16869423
复制相关文章
相似问题
腾讯云开发者
