讓 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).
我認為堆排序可能有用，但我真的不確定。
我不需要代碼只是想法......我會很感激任何幫助
謝謝 :) 如果我有英語錯誤，對不起 :(
uj5u.com熱心網友回復：
我的一般方法是創建 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 的冪也逐漸變小。所以上面的整個運算式呈現為一個 sweet O(n)。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/335889.html
上一篇：回傳頻率元組串列，我哪里做錯了？