在 O(n) 中查找并排序 n 值数组中的 log2(n) 最小值和 log2(n) 最大值
Find and sort in O(n) the log2(n) smallest values and the log2(n) largest values in an array of n values
设 A 为 n 个不同数字（正数和负数）的数组。
我们对 ⌊log_2(n)⌋ 最小值感兴趣，
并且在 ⌊log_2(n)⌋ 个最大值中。
查找计算此 2⌊log_2(n)⌋ 值的算法，
并将它们呈现在排序数组中 (size = 2⌊log_2(n)⌋)
1. the running time of the algorithm must be θ(n),
2. prove that the running time is θ(n).
我想也许堆排序会有用，但我真的不确定。
我不需要代码只是想法...我将不胜感激任何帮助
谢谢 :) 如果我有英文错误请见谅 :(
我的一般方法是创建 2 个堆数据结构，一个用于最大值，一个用于最小值，并在它们中堆化数组 for/in。如果处理得当，堆化是线性时间复杂度的操作。
然后我将从两个堆中提取 ⌊log_2(n)⌋ 项，其中每次提取都具有复杂性 O(log n)。因此，这将为我们提供以下粗略的计算估计：
2 * n + 2 * (log(n))^2
2 * n 两次堆肥操作。
log(n) * log(n) 用于从其中一个堆中提取 log(n) 元素。
2 * (log(n))^2 用于从两个堆中提取 log(n) 个元素。
在大 O 术语中，支配项是 n，因为 log(n) 即使是 2 的幂也逐渐变小。所以上面的整个表达式呈现出一个甜蜜的 O(n).
设 A 为 n 个不同数字（正数和负数）的数组。
我们对 ⌊log_2(n)⌋ 最小值感兴趣，
并且在 ⌊log_2(n)⌋ 个最大值中。
查找计算此 2⌊log_2(n)⌋ 值的算法，
并将它们呈现在排序数组中 (size = 2⌊log_2(n)⌋)
1. the running time of the algorithm must be θ(n),
2. prove that the running time is θ(n).
我想也许堆排序会有用，但我真的不确定。
我不需要代码只是想法...我将不胜感激任何帮助
谢谢 :) 如果我有英文错误请见谅 :(
我的一般方法是创建 2 个堆数据结构，一个用于最大值，一个用于最小值，并在它们中堆化数组 for/in。如果处理得当，堆化是线性时间复杂度的操作。
然后我将从两个堆中提取 ⌊log_2(n)⌋ 项，其中每次提取都具有复杂性 O(log n)。因此，这将为我们提供以下粗略的计算估计：
2 * n + 2 * (log(n))^2
2 * n 两次堆肥操作。
log(n) * log(n) 用于从其中一个堆中提取 log(n) 元素。
2 * (log(n))^2 用于从两个堆中提取 log(n) 个元素。
在大 O 术语中，支配项是 n，因为 log(n) 即使是 2 的幂也逐渐变小。所以上面的整个表达式呈现出一个甜蜜的 O(n).