做网站比较便宜,广州网站建设市场,阳东城乡规划建设局网站,社区门户网站规范化建设【数据结构】建堆算法复杂度分析及TOP-K问题 #x1f525;个人主页#xff1a;大白的编程日记
#x1f525;专栏#xff1a;数据结构 文章目录 【数据结构】建堆算法复杂度分析及TOP-K问题前言一.复杂度分析1.1向下建堆复杂度1.2向上建堆复杂度1.3堆排序复杂度 二.TOP-K问…【数据结构】建堆算法复杂度分析及TOP-K问题 个人主页大白的编程日记
专栏数据结构 文章目录 【数据结构】建堆算法复杂度分析及TOP-K问题前言一.复杂度分析1.1向下建堆复杂度1.2向上建堆复杂度1.3堆排序复杂度 二.TOP-K问题2.1思路分析2.2代码实现 后言 前言 哈喽各位小伙伴大家好上期我们讲了堆排序和建堆算法。今天我们就来分析一下他们的时间复杂度。话不多说,咱们进入正题。向大厂冲锋! 一.复杂度分析
我们都知道堆是一个完全二叉树。那他的高度h和节点数量N有什么关系呢 那我们再来对比一下满二叉树和完全二叉树的高度h. 我们用大O渐进表示法看的话他们两个的高度h都可以认为是logN的量级 所以我们的堆的上下调整可以认为是logN也就是高度次。 因为堆是完全二叉树而满二叉树也是完全二叉树所以为了方便证明 我们使用满二叉树来证明(时间复杂度本来看的就是近似值多几个结点不影响最终结果) 1.1向下建堆复杂度
我们先分别算出第一层到h-1层的节点个数和该层节点的调整次数 然后再推出总的调整次数。
推导
1.2向上建堆复杂度
我们先分别算出第2层到h层的节点个数和该层节点的调整次数 然后再推出总的调整次数。
推导
所以向下建堆的时间复杂度是O(N),向上建堆的复杂度是O(N*logN). 所以以后我们都尽量使用向下调整建堆。因为他的效率更高。
1.3堆排序复杂度
现在我们来看一下我们堆排序的时间复杂度是多少呢
推导 堆排序的复杂度是O(N*logN).
二.TOP-K问题
2.1思路分析 我们的堆除了可以用来排序还可以用来解决经典的TOP-K问题。 TOP-K问题即求数据结合中前K个最大的元素或者最小的元素一般情况下数据量都比较大。 比如专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。 方法一 我们很容易想到直接排序然后取出前K个即可。 但是这个方法有个致命缺陷。 如果数据量非常大排序就不太可取了(可能数据都不能一下子全部加载到内存中)。 我们发现这个方法在数据量太大的时候并不适用。 那有什么其他好的方法吗方法二 最佳的方式就是用堆来解决基本思路如下 1 .用数据集合中前K个元素来建堆 前k个最大的元素则建K个数的小堆 前k个最小的元素则建K个数的大堆 2 . 用剩余的N-K个元素依次与堆顶元素来比较 如果比堆顶元素还要大或小(小堆大 大堆小)则替换堆顶元素然后向下调整重新建堆。 将剩余N-K个元素依次与堆顶元素比完之后堆中剩余的K个元素就是所求的前K个最小或者最大的元素。 为什么呢
证明 我们通过N-K次比较就可以筛选出N-K个不满足最大前K个数的数 剩下在堆的数就是最大的前K个。疑问
我们用反证法可以得知这种情况不存在。
2.2代码实现
生成数据函数 我们先用srand生成不同的种子防止生成的随机数是伪随机数。 然后fopen打开文件。循环生成随机数然后写入文件即可。最后关闭文件。
void CreatData()
{int n 100000;//生成10万个数据srand(time(0));//生成不同的种子FILE* pf fopen(test.txt, w);//打开文件for (int i 0; i n; i){int x rand() % 100001i;//生成随机数fprintf(pf, %d\n, x);//写数据}fclose(pf);//关闭文件pf NULL;
}这样10万个数据就生成好了。
比较函数
我们先接收k。然后开好k个数是堆空间。 然后从文件读取前k个数并填充到堆里面。然后建堆 然后继续读取文件里的数据直到文件末尾(返回EOF) 然后当数据大于堆顶元素是在进堆然后重新调整建堆即可。
void test()
{int k;printf(请输入前K个数);scanf(%d, k);int* a (int*)malloc(sizeof(int) * k);//开空间建堆FILE* pf fopen(test.txt, r);for (int i 0; i k; i){fscanf(pf, %d, a[i]);}//填充数据for (int i (k - 1 - 1) / 2; i 0; i--){AdjustDown(a, k, i);}//建小堆int x;while (fscanf(pf, %d, x) !EOF){if (x a[0]){a[0] x;AdjustDown(a, k, 0);}}//对比for (int i 0; i k; i){printf(%d , a[i]);}//打印
}检验
那我们如何确保这10个数一定是最大的呢万一我们的算法写错不是最大的前10个数怎么办 那我们就可以在不同的地方在一些k标点。 也就是K个很大的数确保他们是最大的前K个。 然后只需要看结果是不是这k个数即可。 大家发现结果就是我们手动给的这10个数。说明我们的程序时没问题的。
后言 这就是建堆算法复杂度分析及TOP-K问题。这里涉及到许多数学知识。大家可以多看几遍证明图。今天就分享到这里。感谢大佬们垂阅咱们下期见拜拜~
