当前位置: 首页 > news >正文

【数据结构】建堆算法复杂度分析及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() % 100001+i;//生成随机数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问题。这里涉及到许多数学知识。大家可以多看几遍证明图。今天就分享到这里。感谢大佬们垂阅!咱们下期见!拜拜~

相关文章:

【数据结构】建堆算法复杂度分析及TOP-K问题

【数据结构】建堆算法复杂度分析及TOP-K问题 &#x1f525;个人主页&#xff1a;大白的编程日记 &#x1f525;专栏&#xff1a;数据结构 文章目录 【数据结构】建堆算法复杂度分析及TOP-K问题前言一.复杂度分析1.1向下建堆复杂度1.2向上建堆复杂度1.3堆排序复杂度 二.TOP-K问…...

Thinkphp5实现前后端通过接口通讯基本操作方法

在ThinkPHP5框架中&#xff0c;实现前后端通过接口通讯是一个常见的需求&#xff0c;尤其是在开发RESTful API时。下面是一个基本的步骤指南&#xff0c;用于设置ThinkPHP5来创建API接口&#xff0c;并使前端能够通过HTTP请求与后端进行通讯。 1. 创建API模块 首先&#xff0…...

Go 语言任务编排 WaitGroup

WaitGroup 是常用的 Go 同步原语之一,用来做任务编排。它要解决的就是并发-等待的问题: 现在有一个 goroutine A 在检查点 ( checkpoint ) 等待一组 goroutine 全部完成它们的任务,如果这些 goroutine 还没全部完成任务,那么 goroutine A 就会被阻塞在检查点,直到所有的 …...

星环科技推出知识库产品 AI PC时代数据交互方式变革

随着企业业务的快速发展&#xff0c;数据量呈爆炸式增长&#xff0c;有效的知识管理成为企业面临的重要问题。企业遇到的普遍问题是大量的结构化、半结构化数据存储在不同的系统中&#xff0c;需要用多种计算机语言进行检索。而大模型彻底改变了人们和数据的交互方式&#xff0…...

10道JVM经典面试题

1、 JVM中&#xff0c;new出来的对象是在哪个区&#xff1f; 2、 说说类加载有哪些步骤&#xff1f; 3、 JMM是什么&#xff1f; 4、 说说JVM内存结构&#xff1f; 5、 MinorGC和FullGC有什么区别&#xff1f; 6、 什么是STW? 7、 什么情况下会发生堆/栈溢出&#xff1f…...

Redisson常用的数据结构及应用场景

Redisson 提供了一系列高级数据结构&#xff0c;这些数据结构封装了 Redis 的原生数据类型&#xff0c;提供了 Java API 的便利性和分布式特性。以下是 Redisson 中一些常用的数据结构&#xff0c;场景还在不断完善中&#xff1a; RBucket&#xff1a;这是一个简单的键值对存储…...

【实现100个unity特效之8】使用ShaderGraph实现2d贴图中指定部分局部发光效果

最终效果 寒冰法师 火焰法师 文章目录 最终效果寒冰法师火焰法师 素材一、功能分析实现方法基本思路Unity的Bloom后处理为什么关键部位白色&#xff1f;最终结果 二、 新建URP项目三、合并图片四、使用PS制作黑白图片方法一 手动涂鸦方法二 魔棒工具1. 拖入图片进PS&#xff0…...

Ubuntu 24.04 LTS Noble安装Docker Desktop简单教程

Docker 为用户提供了在 Ubuntu Linux 上快速创建虚拟容器的能力。但是&#xff0c;那些不想使用命令行管理容器的人可以在 Ubuntu 24.04 LTS 上安装 Docker Desktop GUI&#xff0c;本教程将提供用于设置 Docker 图形用户界面的命令…… Docker Desktop 是一个易于使用的集成容…...

XML 和 SimpleXML 入门教程

XML 和 SimpleXML 入门教程 XML&#xff08;可扩展标记语言&#xff09;是一种用于存储和传输数据的标记语言。它是一种自我描述的语言&#xff0c;允许用户定义自己的标签来表示数据。SimpleXML 是 PHP 中的一个扩展&#xff0c;用于解析和操作 XML 数据。本文将介绍 XML 和 …...

leetcode--链表类题目总结

本文作为刷题时对链表类题目的总结. 常见技巧: 引入虚拟头节点 便于处理边界情况便于对链表操作快慢双指针(判环,找环的入口等)链表逆序(推荐使用 虚拟头节点 头插法 进行逆序) 链表逆序( 头插法 虚拟头节点):链表内指定区间反转_牛客题霸_牛客网 虚拟节点:合并…...

打卡第22天------回溯算法

开始学习了,希望我可以尽快成功上岸! 一、回溯理论基础 什么是回溯法?回溯法也可以叫做回溯搜索法,它是一种搜索的方式。 回溯是递归的副产品,只要有递归就会有回溯。 回溯法的效率回溯法的本质是穷举,穷举所有可能,然后找出我们想要的答案。如果想让回溯法高效一些,可…...

Ubuntu对比两个文件内容有什么区别?

在Ubuntu&#xff08;或任何基于Linux的系统&#xff09;中&#xff0c;你可以使用多种命令行工具来比较两个文件的内容差异。以下是一些常用的方法&#xff1a; 1. **diff 命令**&#xff1a; diff 是Linux中用于比较两个文件差异的标准工具。它逐行比较文件&#xff0c;并显示…...

python:本机摄像头目标检测实时推理(使用YOLOv8n模型)

本文将介绍如何使用本机摄像头进行目标检测实时推理的python代码。 文章目录 一、下载YOLO权重文件二、环境配置三、完整代码 一、下载YOLO权重文件 https://github.com/ultralytics/ultralytics?tabreadme-ov-file 拉到网页最下面&#xff0c;选择适合的模型&#xff0c;下…...

Spark实时(四):Strctured Streaming简单应用

文章目录 Strctured Streaming简单应用 一、Output Modes输出模式 二、Streaming Table API 三、​​​​​​​​​​​​​​Triggers 1、​​​​​​​unspecified&#xff08;默认模式&#xff09; 2、​​​​​​​​​​​​​​Fixed interval micro-batches&am…...

SpringBoot上传超大文件导致OOM,完美问题解决办法

问题描述 报错: Caused by: java.lang.OutOfMemoryError at java.io.ByteArrayOutputStream.hugeCapacity(ByteArrayOutputStream.java:123) ~[?:1.8.0_381] at java.io.ByteArrayOutputStream.grow(ByteArrayOutputStream.java:117) ~[?:1.8.0_381] at java.…...

PyTorch 的各个核心模块和它们的功能

1. torch 核心功能 张量操作&#xff1a;PyTorch 的张量是一个多维数组&#xff0c;类似于 NumPy 的 ndarray&#xff0c;但支持 GPU 加速。数学运算&#xff1a;提供了各种数学运算&#xff0c;包括线性代数操作、随机数生成等。自动微分&#xff1a;torch.autograd 模块用于…...

Java开发之LinkedList源码分析

#来自ゾフィー&#xff08;佐菲&#xff09; 1 简介 LinkedList 的底层数据结构是双向链表。可以当作链表、栈、队列、双端队列来使用。有以下特点&#xff1a; 在插入或删除数据时&#xff0c;性能好&#xff1b;允许有 null 值&#xff1b;查询效率不高&#xff1b;线程不安…...

外卖霸王餐系统架构怎么选?

在当今日益繁荣的外卖市场中&#xff0c;外卖霸王餐作为一种独特的营销策略&#xff0c;受到了众多商家的青睐。然而&#xff0c;要想成功实施外卖霸王餐活动&#xff0c;一个安全、稳定且高效的架构选择至关重要。本文将深入探讨外卖霸王餐架构的选择&#xff0c;以期为商家提…...

AV1技术学习:Transform Coding

对预测残差进行变换编码&#xff0c;去除潜在的空间相关性。VP9 采用统一的变换块大小设计&#xff0c;编码块中的所有的块共享相同的变换大小。VP9 支持 4 4、8 8、16 16、32 32 四种正方形变换大小。根据预测模式选择由一维离散余弦变换 (DCT) 和非对称离散正弦变换 (ADS…...

Git操作指令

Git操作指令 一、安装git 1、设置配置信息&#xff1a; # global全局配置 git config --global user.name "Your username" git config --global user.email "Your email"2、查看git版本号 git -v # or git --version3、查看配置信息&#xff1a; git…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)

文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法&#xff0c;当前调用一个医疗行业的AI识别算法后返回…...

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)

Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败&#xff0c;具体原因是客户端发送了密码认证请求&#xff0c;但Redis服务器未设置密码 1.为Redis设置密码&#xff08;匹配客户端配置&#xff09; 步骤&#xff1a; 1&#xff09;.修…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!

简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求&#xff0c;并检查收到的响应。它以以下模式之一…...

技术栈RabbitMq的介绍和使用

目录 1. 什么是消息队列&#xff1f;2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf

FTP 客服管理系统 实现kefu123登录&#xff0c;不允许匿名访问&#xff0c;kefu只能访问/data/kefu目录&#xff0c;不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...

消息队列系统设计与实践全解析

文章目录 &#x1f680; 消息队列系统设计与实践全解析&#x1f50d; 一、消息队列选型1.1 业务场景匹配矩阵1.2 吞吐量/延迟/可靠性权衡&#x1f4a1; 权衡决策框架 1.3 运维复杂度评估&#x1f527; 运维成本降低策略 &#x1f3d7;️ 二、典型架构设计2.1 分布式事务最终一致…...