2
Top K最小選擇算法 - O（n + k log n）vs O（n log k）我對Top K算法提出這個問題。我認爲O（n + k log n）應該更快，因爲例如，如果嘗試插入k = 300和n = 100000000例如，我們可以看到O（n + k log n）更小。但是，當我使用C++進行基準測試時，它顯示出O（n log k）快了2倍以上。下面是完整的基準程序：對於k << N
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <ctime>
#include <cstdlib>
using namespace std;
int RandomNumber() { return rand(); }
vector<int> find_topk(int arr[], int k, int n)
{
make_heap(arr, arr + n, greater<int>());
vector<int> result(k);
for (int i = 0; i < k; ++i)
{
result[i] = arr[0];
pop_heap(arr, arr + n - i, greater<int>());
}
return result;
}
vector<int> find_topk2(int arr[], int k, int n)
{
make_heap(arr, arr + k, less<int>());
for (int i = k; i < n; ++i)
{
if (arr[i] < arr[0])
{
pop_heap(arr, arr + k, less<int>());
arr[k - 1] = arr[i];
push_heap(arr, arr + k, less<int>());
}
}
vector<int> result(arr, arr + k);
return result;
}
int main()
{
const int n = 220000000;
const int k = 300;
srand (time(0));
int* arr = new int[n];
generate(arr, arr + n, RandomNumber);
// replace with topk or topk2
vector<int> result = find_topk2(arr, k, n);
copy(result.begin(), result.end(), ostream_iterator<int>(cout, "\n"));
return 0;
}
find_topk的做法是建立大小爲n的完整堆，在O（N），然後刪除的堆k倍澳頂部元件（log n）的。 find_topk2的方法是構建一個大小爲k（O（k））的堆，使得max元素位於頂部，然後從k位置到n，比較是否有任何元素小於頂部元素，如果是彈出頂部元素，並推入新的元素，這意味着n次O（log k）。 這兩種方法的寫法都非常相似，所以我不相信任何實現細節（如創建臨時對象等）都會導致算法以外的算法和數據集（隨機）。
我實際上可以剖析基準測試的結果，並且可以看到find_topk實際上比find_topk2多次調用比較運算符。但是我更關心理論複雜性的推理。所以有兩個問題。
- 無視執行或基準，期待O（n + k log n）應該比O（n log k）好嗎？如果我錯了，請解釋爲什麼以及如何推理，以便我可以看到O（n log k）實際上更好。
- 如果我沒有錯，期望沒有1.那麼爲什麼我的基準顯示不然？
我希望你知道nth_element/partial_sort算法，並只爲了好玩。 –
'partial_sort' /'partial_sort_copy'在這個syntetic測試中的運行時間與您的'find_topk2'完全相同 – sehe
yes我知道find_topk2可以通過partial_sort進行替換。但我正在這樣做，使算法更加明確。 – ryaner