- Java 双重比较
- java - 比较器与 Apache BeanComparator
- Objective-C 完成 block 导致额外的方法调用?
- database - RESTful URI 是否应该公开数据库主键?
我问的是关于 Top K 算法的问题。我认为 O(n + k log n) 应该更快,因为……例如,如果您尝试插入 k = 300 和 n = 100000000,我们可以看到 O(n + k log n)更小。
但是,当我使用 C++ 进行基准测试时,它显示 O (n log k) 快了 2 倍以上。这是完整的基准测试程序:
#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 的方法是在 O(n) 中构建一个大小为 n 的完整堆,然后移除堆顶元素 k 次 O(log n)。find_topk2的做法是建立一个大小为k(O(k))的堆,使得最大元素在最顶层,然后从k到n,比较是否有元素小于顶层元素,如果有则pop顶部元素,然后推送新元素,这意味着 n 倍 O(log k)。这两种方法的编写方式非常相似,所以我认为除了算法和数据集(随机的)之外,任何实现细节(如创建临时对象等)都不会造成差异。
我实际上可以分析基准测试的结果,并且可以看到 find_topk 实际上调用比较运算符的次数比 find_topk2 多很多。但我对理论复杂性的推理更感兴趣。所以有两个问题。
最佳答案
多个变量中的大 O 很复杂,因为您需要假设变量如何相互缩放,因此您可以明确地将极限取为无穷大。
如果例如。 k ~ n^(1/2),然后 O(n log k) 变为 O(n log n) 并且 O(n + k log n) 变为 O(n + n^(1/2) log n) = O (n),哪个更好。
如果 k ~ log n,则 O(n log k) = O(n log log n) 和 O(n + k log n) = O(n),哪个更好。请注意,log log 2^1024 = 10,因此对于任何实际 n,隐藏在 O(n) 中的常量可能大于 log log n。
如果 k = 常数,则 O(n log k) = O(n) 和 O(n + k log n) = O(n),这是相同的。
但是常量起着很大的作用:例如,构建一个堆可能需要读取数组 3 次,而构建一个长度为 k 的优先级队列只需要遍历一次数组,以及一个小的常数次日志k 用于查找。
因此不清楚哪个“更好”,尽管我的快速分析倾向于表明 O(n + k log n) 在对 k 的温和假设下表现更好。
例如,如果 k 是一个非常小的常量(比如 k = 3),那么我敢打赌,make_heap
方法在真实世界数据上的表现比优先级队列更差。
明智地使用渐近分析,最重要的是,在得出结论之前分析您的代码。
关于c++ - Top K 最小选择算法 - O (n + k log n) vs O (n log k) for k << N,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6669838/
我看到以下宏 here . static const char LogTable256[256] = { #define LT(n) n, n, n, n, n, n, n, n, n, n, n,
这个问题不太可能帮助任何 future 的访问者;它只与一个小的地理区域、一个特定的时间点或一个非常狭窄的情况有关,这些情况并不普遍适用于互联网的全局受众。为了帮助使这个问题更广泛地适用,visit
所以我得到了这个算法我需要计算它的时间复杂度 这样的 for i=1 to n do k=i while (k<=n) do FLIP(A[k]) k
n 的 n 次方(即 n^n)是多项式吗? T(n) = 2T(n/2) + n^n 可以用master方法求解吗? 最佳答案 它不仅不是多项式,而且比阶乘还差。 O(n^n) 支配 O(n!)。同样
我正在研究一种算法,它可以在带有变音符号的字符(tilde、circumflex、caret、umlaut、caron)及其“简单”字符之间进行映射。 例如: ń ǹ ň ñ ṅ ņ ṇ
嗯..我从昨天开始学习APL。我正在观看 YouTube 视频,从基础开始学习各种符号,我正在使用 NARS2000。 我想要的是打印斐波那契数列。我知道有好几种代码,但是因为我没有研究过高深的东西,
已关闭。这个问题是 off-topic 。目前不接受答案。 想要改进这个问题吗? Update the question所以它是on-topic用于堆栈溢出。 已关闭12 年前。 Improve th
谁能帮我从 N * N * N → N 中找到一个双射数学函数,它接受三个参数 x、y 和 z 并返回数字 n? 我想知道函数 f 及其反函数 f',如果我有 n,我将能够通过应用 f'(n) 来
场景: 用户可以在字符串格式的方程式中输入任意数量的括号对。但是,我需要检查以确保所有括号 ( 或 ) 都有一个相邻的乘数符号 *。因此 3( 应该是 3*( 和 )3 应该是 )*3。 我需要将所有
在 Java 中,表达式: n+++n 似乎评估为等同于: n++ + n 尽管 +n 是一个有效的一元运算符,其优先级高于 n + n 中的算术 + 运算符。因此编译器似乎假设运算符不能是一元运算符
当我阅读 this 问题我记得有人曾经告诉我(很多年前),从汇编程序的角度来看,这两个操作非常不同: n = 0; n = n - n; 这是真的吗?如果是,为什么会这样? 编辑: 正如一些回复所指出
我正在尝试在reveal.js 中加载外部markdown 文件,该文件已编写为遵守数据分隔符语法: You can write your content as a separate file and
我试图弄清楚如何使用 Javascript 生成一个随机 11 个字符串,该字符串需要特定的字母/数字序列,以及位置。 ----------------------------------------
我最近偶然发现了一个资源,其中 2T(n/2) + n/log n 类型 的递归被 MM 宣布为无法解决。 直到今天,当另一种资源被证明是矛盾的(在某种意义上)时,我才接受它作为引理。 根据资源(下面
关闭。此题需要details or clarity 。目前不接受答案。 想要改进这个问题吗?通过 editing this post 添加详细信息并澄清问题. 已关闭 8 年前。 Improve th
我完成的一个代码遵循这个模式: for (i = 0; i < N; i++){ // O(N) //do some processing... } sort(array, array + N
有没有办法证明 f(n) + g(n) = theta(n^2) 还是不可能?假设 f(n) = theta(n^2) & g(n) = O(n^2) 我尝试了以下方法:f(n) = O(n^2) &
所以我目前正在尝试计算我拥有的一些数据的 Pearson R 和 p 值。这是通过以下代码完成的: import numpy as np from scipy.stats import pearson
ltree 列的默认排序为文本。示例:我的表 id、parentid 和 wbs 中有 3 列。 ltree 列 - wbs 将 1.1.12, 1.1.1, 1.1.2 存储在不同的行中。按 wbs
我的目标是编写一个程序来计算在 python 中表示数字所需的位数,如果我选择 number = -1 或任何负数,程序不会终止,这是我的代码: number = -1 cnt = 0 while(n
我是一名优秀的程序员,十分优秀!