c – multimap的时间复杂性问题
|
我创建了一个程序来查找数字列表的中位数.数字列表是动态的,可以删除和插入数字(可以输入重复的数字),在此期间,重新评估和打印新的中位数.
我使用multimap创建了这个程序,因为 1)它已被分类的好处, 条目删除次数的约束(表示为N)是：0 <0. N <= 100,000. 我写的程序工作并打印出正确的中位数,但速度不够快.我知道unsorted_multimap比multimap快,但是unsorted_multimap的问题是我必须对它进行排序.我必须对它进行排序,因为找到你需要有一个排序列表的中位数.所以我的问题是,使用unsorted_multimap然后快速排序条目是否可行,或者这只是荒谬的？使用矢量,快速导航矢量和使用二分搜索会更快吗？或者也许我忘记了一些我甚至都没想过的神话般的解决方案. 虽然我不是C的新手,但我会承认,我的时间复杂性技巧在某种程度上是医学上的. 我越是看自己的问题,我越开始认为只使用带快速排序和二进制搜索的向量会更好,因为数据结构基本上已经实现了向量. 解决方法
如果你的目的是跟踪动态的中位数,当插入/删除元素时,你应该使用最小堆和最大堆.每一个都包含一半的元素……几天前有一个相关的问题：
How to implement a Median-heap
但是,如果您需要搜索特定值以删除元素,则仍需要某种地图. 你说它很慢.每次需要中位数时,您是否从地图的开头迭代到第(N / 2)个元素？你不需要.您可以通过始终保持指向它的迭代器以及小于该值的元素数量的计数器来跟踪中值.每次插入/删除时,将new / old元素与中位数进行比较并更新迭代器和计数器. 另一种看待它的方式是两个包含每个元素一半的多重图.一个保持元素小于中位数(或相等),另一个保持较大的元素.堆更有效地做到这一点,但他们不支持搜索. 如果您只需要几次中位数,则可以使用“选择”算法.它在Sedgewick的书中有所描述.平均需要O(n)时间.它类似于快速排序但不完全排序.它只是用随机枢轴对阵列进行分区,直到最终它在一侧“选择”较小的m个元素(m =(n 1)/ 2).然后你搜索那些m元素中最大的元素,这是中位数. （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |