Fra*_*Jr. 3 algorithm median
我们如何删除具有时间复杂度O(log n)的集合的中值？有些想法？
sup*_*cat 18
如果对集合进行排序,则查找中值需要O(1)项检索.如果项目是任意顺序的,则无法在不检查大部分项目的情况下确定地确定中位数.如果一个人检查了大部分但不是全部的项目,那么将允许人们保证中位数将在某个范围内[如果列表包含重复项,则上限和下限可能匹配],但检查大多数项目列表中的项目意味着O(n)项目检索.
如果一个集合中的信息没有完全排序,但已知某些排序关系,那么所需的时间可能需要O(1)和O(n)项目检索之间的任何时间,具体取决于已知排序的性质关系.
rwo*_*ong 5
对于未排序的列表,重复执行O(n)部分排序,直到位于中间位置的元素已知.但这至少是O(n).
是否有关于要排序的元素的信息？
归档时间：
15 年，9 月 前
查看次数：
11509 次
最近记录：
12 年，9 月 前