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

二叉树与堆相关的时间复杂度问题

目录

满二叉树与完全二叉树高度h和树中节点个数N的关系

向上调整算法:

介绍:

复杂度推导:

向下调整算法:

介绍:

复杂度推导:

向上调整建堆:

介绍:

复杂度推导:

向下调整建堆:

介绍:

复杂度推导:


满二叉树与完全二叉树高度h和树中节点个数N的关系

向上调整算法:

介绍:

函数功能:将堆通过向上调整算法使堆成为小堆(父亲<孩子)或大堆(父亲>孩子),堆内父亲=(孩子-1)/2。只要孩子还在堆范围内,就不断判断孩子与父亲的关系。若想设置小堆,则孩子<父亲就执行交换;若想设置大堆,则孩子>父亲就执行交换。

函数参数:HeapDataType * a—>堆内数据类型首元素的指针  int child—>堆底元素(孩子)

函数返回值:

void AdjustUp(HeapDataType* a, int child)
{int parent = (child - 1) / 2;while (child > 0){if (a[child] > a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}

复杂度推导:

一次向上调整最多调整高度次数,根据满二叉树h=log(N+1),完全二叉树h=log(N)+1,而时间复杂度计算的是最大情况的数量级,所以一次向上调整的复杂度为O(logN)


向下调整算法:

介绍:

函数功能:将堆通过向下调整算法使堆成为小堆(父亲<孩子)或大堆(父亲>孩子),使用假设法先假定要交换的元素为左孩子,child=parent*2+1,若右孩子>左孩子,则需交换的元素为parent*2+1+1。只要孩子还在堆范围内,就不断判断孩子与父亲的关系。若想设置小堆,则孩子<父亲就执行交换;若想设置大堆,则孩子>父亲就执行交换。

函数参数:HeapDataType * a—>堆内数据类型首元素的指针  int n —>堆内元素个数          int parent—>堆顶元素(父亲)

函数返回值:

void Adjustdown(HeapDataType* a, int n, int parent)
{size_t child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child + 1] < a[child]){child++;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

复杂度推导:

一次向下调整最多调整高度次数,根据满二叉树h=log(N+1),完全二叉树h=log(N)+1,而时间复杂度计算的是最大情况的数量级,所以一次向下调整的复杂度为O(logN)


向上调整建堆:

介绍:

前提:上几层都是堆

先将数组内所有元素插入堆结构内,再从第一个元素到最后一个元素进行遍历,对每个元素使用向上调整算法,使堆结构成为大堆/小堆

复杂度推导:


向下调整建堆:

介绍:

前提:左右子树都是堆

先将数组内所有元素插入堆结构内,再从最后一个父亲的位置到第一个父亲的位置进行遍历,对每个元素使用向下调整算法,使堆结构成为大堆/小堆

复杂度推导:

相关文章:

二叉树与堆相关的时间复杂度问题

目录 满二叉树与完全二叉树高度h和树中节点个数N的关系 向上调整算法&#xff1a; 介绍&#xff1a; 复杂度推导&#xff1a; 向下调整算法&#xff1a; 介绍&#xff1a; 复杂度推导&#xff1a; 向上调整建堆&#xff1a; 介绍&#xff1a; 复杂度推导&#xff1a;…...

goLang小案例-获取从控制台输入的信息

goLang小案例-获取从控制台输入的信息 1. 案例代码展示 package mainimport ("bufio""fmt""log""os" )var pl fmt.Printlnfunc main() {//控制台输出欢迎提示pl("Hello Go")fmt.Print("what is your name? ")…...

1-5题查询 - 高频 SQL 50 题基础版

目录 1. 相关知识点2. 例题2.1.可回收且低脂的产品2.2.寻找用户推荐人2.3.大的国家2.4. 文章浏览 I2.5. 无效的推文 1. 相关知识点 sql判断&#xff0c;不包含null&#xff0c;判断不出来distinct是通过查询的结果来去除重复记录ASC升序计算字符长度 CHAR_LENGTH() 或 LENGTH(…...

Modbus协议转Profinet协议网关模块连智能仪表与PLC通讯

一、现场需求&#xff1a;PLC作为控制器&#xff0c;仪表设备做为执行设备&#xff0c;执行设备能够实时响应PLC传来的指令&#xff0c;并且向PLC回馈数据&#xff0c;从而达到PLC对仪表设备进行控制和监测&#xff0c;实现对生产过程的精准控制。 二、解决方案&#xff1a;通过…...

新手必学:TikTok视频标签的使用方法

想让你的TikTok视频火起来&#xff0c;就得用对标签。标签能帮你的作品被更多人看到&#xff0c;也更有利于推广&#xff0c;可以为品牌增加曝光度、吸引更多观众、提高转化率和借势热门话题。那么应该如何选择标签并使用标签呢&#xff0c;看完这篇分享你或许会有所启发&#…...

AI是在帮助开发者还是取代他们

近年来&#xff0c;AI工具在软件开发和数据分析领域的应用日益广泛&#xff0c;它们对开发者的日常工作产生了深远的影响。AI工具通过自动化处理大量数据、优化代码质量、提高测试效率等方式&#xff0c;极大地提升了开发者的工作效率。然而&#xff0c;这同时也对开发者的传统…...

【后端面试题】【中间件】【NoSQL】MongoDB查询过程、ESR规则、覆盖索引的优化

任何中间件的面试说到底都是以高可用、高性能和高并发为主&#xff0c;而高性能和高并发基本是同时存在的。 性能优化一直被看作一个高级面试点&#xff0c;因为只有对原理了解得很透彻的人&#xff0c;在实践中才能找准性能优化的关键点&#xff0c;从而通过各种优化手段解决性…...

使用c++函数式编程实现Qt信号槽机制

问题背景 在下面的代码中&#xff0c;Input输入器 输入数据&#xff0c;希望A和B 接收数据。但使用的赋值&#xff0c;导致in.a和a只是拷贝数据&#xff0c;而不是同一个对象&#xff0c;使得数据不同步。 #include <iostream> struct A {int age 32; }; struct B {int …...

【Android】Activity子类之间的区别

从底层往顶层的继承顺序依次是&#xff1a; Activity&#xff0c;最原始的Activity androidx.core.app.ComponentActivity&#xff0c;仅仅优化了一个关于KeyEvent的拦截问题&#xff0c;一般不继承这个类 androidx.activity.ComponentActivity&#xff0c;支持和Android Arc…...

在 Mac 上使用 MLX 微调微软 phi3 模型

微调大语言模型是常见的需求&#xff0c;由于模型参数量大&#xff0c;即使用 Lora/Qlora 进行微调也需要 GPU 显卡&#xff0c;Mac M系是苹果自己的 GPU&#xff0c;目前主流的框架还在建立在 CUDA 的显卡架构&#xff0c;也就是主要的卡还是来自英伟达。如果要用 Mac 来做训练…...

【JavaEE】多线程代码案例(2)

&#x1f38f;&#x1f38f;&#x1f38f;个人主页&#x1f38f;&#x1f38f;&#x1f38f; &#x1f38f;&#x1f38f;&#x1f38f;JavaEE专栏&#x1f38f;&#x1f38f;&#x1f38f; &#x1f38f;&#x1f38f;&#x1f38f;上一篇文章&#xff1a;多线程代码案例(1)&a…...

Halcon支持向量机

一 支持向量机 1 支持向量机介绍&#xff1a; 支持向量机(Support Vector Machine&#xff0c;SVM)是Corinna Cortes和Vapnik于1995年首先提出的&#xff0c;它在解决小样本、非线性及高维模式识别表现出许多特有的优势。 2 支持向量机原理: 在n维空间中找到一个分类超平面…...

【Python机器学习】模型评估与改进——在模型选择中使用评估指标

我们通常希望&#xff0c;在使用GridSearchCV或cross_val_score进行模型选择时能够使用AUC等指标。scikit-learn提供了一种非常简单的实现方法&#xff0c;那就是scoring参数&#xff0c;它可以同时用于GridSearchCV和cross_val_score。你只需要提供一个字符串&#xff0c;用于…...

【C语言】union 关键字

在C语言中&#xff0c;union关键字用于定义联合体。联合体是一种特殊的数据结构&#xff0c;它允许不同的数据类型共享同一段内存。所有联合体成员共享同一个内存位置&#xff0c;因此联合体的大小取决于其最大成员的大小。 定义和使用联合体 基本定义 定义一个联合体类型时…...

电脑回收站删除的文件怎么恢复?5个恢复方法详解汇总!

电脑回收站删除的文件怎么恢复&#xff1f;在我们日常使用电脑的过程中&#xff0c;难免会遇到误删文件的情况。一旦发现自己误删文件了&#xff0c;先不要着急&#xff0c;还是有很多方法可以找回的。市面上还是有很多好用的文件恢复软件可以使用&#xff0c;具体介绍如下。 本…...

mac 安装cnpm 淘宝镜像记录

mac 安装cnpm 淘宝镜像记录 本文介绍了在安装cnpm时遇到权限问题的解决方案&#xff0c;包括使用sudo&#xff0c;处理SSL证书过期&#xff0c;以及因版本不一致导致的错误处理方法&#xff0c;步骤包括设置npm配置、卸载和重新安装cnpm到特定版本。 安装 npm install cnpm …...

ArcGIS Pro SDK (七)编辑 11 撤销重做

ArcGIS Pro SDK &#xff08;七&#xff09;编辑 11 撤销&重做 文章目录 ArcGIS Pro SDK &#xff08;七&#xff09;编辑 11 撤销&重做1 撤消/重做最近的操作 环境&#xff1a;Visual Studio 2022 .NET6 ArcGIS Pro SDK 3.0 1 撤消/重做最近的操作 //撤销 if (MapV…...

Excel 中的元素定位:相对定位、绝对定位和混合定位

在Excel中&#xff0c;单元格引用有三种主要类型&#xff1a;相对定位、绝对定位和混合定位。 这些类型主要用于公式和函数中&#xff0c;决定在复制或拖动公式时引用如何变化。 1. 相对定位 相对定位指的是不带“$”符号的单元格引用&#xff0c;例如 A1。 这种引用方式在…...

Idea2024安装后点击无响应

问题 最近因工作需要&#xff0c;升级一下 idea 版本&#xff0c;之前一直使用的是2020版本&#xff0c;下载最新的2024版本&#xff08;下载的 zip 包免安装模式&#xff0c;之前使用的2020版本也是免安装的&#xff0c;因为是免安装的&#xff0c;所以之前的版本也没有删除&…...

如何提高实验室分析结果的准确性呢

要提高实验室分析结果的准确性&#xff0c;可以从以下几个方面着手&#xff1a; 1、选择合适的实验方法 不同的实验方法具有不同的优缺点&#xff0c;实验方法的准确度直接影响测定结果的准确度。因此&#xff0c;在选择实验方法时&#xff0c;需要根据实验目的、实验原理、实…...

HTML 语义化

目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案&#xff1a; 语义化标签&#xff1a; <header>&#xff1a;页头<nav>&#xff1a;导航<main>&#xff1a;主要内容<article>&#x…...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

51c自动驾驶~合集58

我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留&#xff0c;CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制&#xff08;CCA-Attention&#xff09;&#xff0c;…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上&#xff0c;开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识&#xff0c;在 vs 2017 平台上&#xff0c;进行 ASP.NET 应用程序和简易网站的开发&#xff1b;初步熟悉开发一…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

CentOS下的分布式内存计算Spark环境部署

一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架&#xff0c;相比 MapReduce 具有以下核心优势&#xff1a; 内存计算&#xff1a;数据可常驻内存&#xff0c;迭代计算性能提升 10-100 倍&#xff08;文档段落&#xff1a;3-79…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)

设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile&#xff0c;新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...