我们如何去除时间复杂度为 O(log n) 的集合的中位数？一些想法？
最佳答案
如果集合已排序，找到中位数需要 O(1) 项检索。如果项目的顺序是任意的，则在不检查大多数项目的情况下将无法确定地识别中位数。如果检查了大部分但不是全部项目，则可以保证中位数在某个范围内 [如果列表包含重复项，上限和下限可能匹配]，但检查大部分列表中的项目意味着 O(n) 项检索。
如果集合中的信息未完全排序，但某些排序关系已知，则所需时间可能需要 O(1) 到 O(n) 项检索之间的任何时间，具体取决于信息的性质已知的排序关系。
关于algorithm - O(log n) 中的中值算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3632297/