为不同的数据结构查找 n/2 最小值的最坏情况复杂度是多少？
对于不同的数据结构，例如链表、数组（排序/未排序、树等）大小为 n 的数据结构，在每个数据结构中查找 n/2 个最小值的最坏情况时间复杂度是多少？ 它与查找操作的复杂度相同吗？
编辑：那么，这些数据结构的复杂性是多少？ 未排序的链表、未排序的数组、展开树和哈希表？
For different data structures such as linked lists, arrays (sorted/unsorted, trees etc. of size n, what is the worst-case time-complexity of finding the n/2 smallest values in each of them?
Is it the same as the complexity for Find operations?
Edit: So, what's the complexity for these data structures?
Unsorted Linked list, unsorted array, splay trees and hash tables?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
未必。例如，对于排序数组，您可以在常数时间内找到 n/2 个最小值。
Not necessarily. For instance, for a sorted array you can find the n/2 smallest values in constant time.
它完全取决于数据结构，例如是否已排序。
如果你考虑一棵平衡树，找到 n/2 最小值将是......“根“左边”的所有值。
你不能概括它那么多，它完全取决于数据结构。
It completly depends on the data structure, and wether it's sorted or not, for instance.
If you consider a balanced tree, finding the n/2 smallest values would be... "all the values to the "left" of the root.
You cannot generalize it quite as much, it depends fully on the data structure.
如果不指定算法或至少数据结构，就不可能指定问题的最坏情况复杂性。如果不使用更合适的中间存储结构，有些数据结构的排序绝对是一场噩梦。例如，堆栈比数组更难排序，因为您无法随机交换元素。
将其与诸如 BogoSort 之类的算法相结合，您可以获得一些令人印象深刻的结果（因为缺乏更好的算法）字）最坏情况的复杂性数字...
It is impossible to specify a worst case complexity for a problem without specifying the algorithm, or at least the data structure. There are data structures that are an absolute nightmare to sort without using a more suitable structure for intermediate storage. Stacks, for example, are significantly harder to sort than arrays, because you cannot swap elements at random.
Combine that with an algorithm such as BogoSort and you can get some pretty impressive (for lack of a better word) worst case complexity figures...