这个算法不会在 O(m log n) 中 运行 吗？
Wouldn't this algorithm run in O(m log n)?
我正在处理来自
Glassdoor Software Engineer
问题是
Given a list of one million numbers, how will you find the top n numbers from the list in an efficient way
这是作者从同一个 link
中给出的解决方案
- 创建一个最小堆
- 取出 m 个元素中的前 n 个元素并放入堆中 (O(n))
- 对于剩余的每(m-n)个元素，如果大于堆的find-min，则插入堆，删除min。 （最坏情况 O((m-n)log n) 如果列表已排序。
最终结果是您可以在 O(n) 内存使用和最坏情况下执行此操作 O((m-n)logn) 运行时间。
我同意作者的算法以及作者对该算法 space 复杂性的评估。我有问题的是作者对 运行 插入堆的时间和总时间的分析
对于步骤 "take first n of m elements and place in the heap"，那不是 运行 在 O(nlogn) 中？至少根据我的 class 笔记 Heap Add, insertion would be O(logn) and because you are inserting n elements, the runtime of that whole step would be O(nlogn).
Taking that into consideration, wouldn't the overall runtime of this entire algorithm be, using big oh addition from Big Oh Addition
O(nlogn + (m-n)logn) = O(mlogn)
For the step "take first n of m elements and place in the heap", wouldn't that run in O(nlogn)?
不一定。您可以从 O(n) 中的 n 个元素创建一个堆。请参阅 here 了解如何实现。
所以你有 O(n + (m - n)log n) = O((m - n)log n) = O(m log n)。只有当 n 被认为是常数时，最后一步才是正确的，否则你应该像作者那样保持 m - n。
后续问题：你能在O(m)中解决整个问题吗？
使用这种方法构建堆，是的，但是有一个 O(n) 算法可以将数组转换为堆。有关详细信息，请参阅 http://en.wikipedia.org/wiki/Binary_heap#Building_a_heap。
也就是说，这个问题存在 O(m) 时间、O(n) 内存解决方案，例如由番石榴的Ordering.leastOf。一种实现是
- 创建一个缓冲区，一个大小为 2n 的数组
- 遍历原始数组，将元素添加到缓冲区
- 每当缓冲区已满时，使用 O(n) 快速选择仅保留缓冲区中最高的 n 个元素并丢弃其余元素。
- 使用一个最终快速选择从缓冲区中提取最高的 n 个元素
这需要 O(m/n) 次快速选择，每次都需要 O(n) 次，总时间为 O(m) 次。
我正在处理来自 Glassdoor Software Engineer
问题是
Given a list of one million numbers, how will you find the top n numbers from the list in an efficient way
这是作者从同一个 link
中给出的解决方案- 创建一个最小堆
- 取出 m 个元素中的前 n 个元素并放入堆中 (O(n))
- 对于剩余的每(m-n)个元素，如果大于堆的find-min，则插入堆，删除min。 （最坏情况 O((m-n)log n) 如果列表已排序。
最终结果是您可以在 O(n) 内存使用和最坏情况下执行此操作 O((m-n)logn) 运行时间。
我同意作者的算法以及作者对该算法 space 复杂性的评估。我有问题的是作者对 运行 插入堆的时间和总时间的分析
对于步骤 "take first n of m elements and place in the heap"，那不是 运行 在 O(nlogn) 中？至少根据我的 class 笔记 Heap Add, insertion would be O(logn) and because you are inserting n elements, the runtime of that whole step would be O(nlogn).
Taking that into consideration, wouldn't the overall runtime of this entire algorithm be, using big oh addition from Big Oh Addition
O(nlogn + (m-n)logn) = O(mlogn)
For the step "take first n of m elements and place in the heap", wouldn't that run in O(nlogn)?
不一定。您可以从 O(n) 中的 n 个元素创建一个堆。请参阅 here 了解如何实现。
所以你有 O(n + (m - n)log n) = O((m - n)log n) = O(m log n)。只有当 n 被认为是常数时，最后一步才是正确的，否则你应该像作者那样保持 m - n。
后续问题：你能在O(m)中解决整个问题吗？
使用这种方法构建堆，是的，但是有一个 O(n) 算法可以将数组转换为堆。有关详细信息，请参阅 http://en.wikipedia.org/wiki/Binary_heap#Building_a_heap。
也就是说，这个问题存在 O(m) 时间、O(n) 内存解决方案，例如由番石榴的Ordering.leastOf。一种实现是
- 创建一个缓冲区，一个大小为 2n 的数组
- 遍历原始数组，将元素添加到缓冲区
- 每当缓冲区已满时，使用 O(n) 快速选择仅保留缓冲区中最高的 n 个元素并丢弃其余元素。
- 使用一个最终快速选择从缓冲区中提取最高的 n 个元素
这需要 O(m/n) 次快速选择，每次都需要 O(n) 次，总时间为 O(m) 次。