算法笔记(二)—— 认识N(logN)的排序算法
递归行为的时间复杂度估算

整个递归过程是一棵多叉树,递归过程相当于利用栈做了一次后序遍历。
对于master公式,T(N)表明母问题的规模为N,T(N/b)表明每次子问题的规模,a为调用次数,加号后面表明,除去调用之外,剩余语句的复杂度是多少,算出d。根据上次三个判断公式进行算法时间复杂度计算。
归并排序(递归实现)
求出中点位置,先将左边部分排好序,再将右侧部分排好序,再整合(双指针),使得整体有序。
时间复杂度O(NlogN) ;空间复杂度O(N)
小和问题

看某个数右侧有多少数比该数大,那么就有这么多个该数对最后结果造成贡献(使用归并排序,在归并过程中进行计算)。和传统merge相比,在于左组数等于右组数时,在小和问题中一定要先拷贝右组的数。
逆序对问题

同小和问题,只不过换成了判断左数组的数大于右数组的数。
315. 计算右侧小于当前元素的个数 - 力扣(LeetCode)
https://leetcode.cn/problems/count-of-smaller-numbers-after-self/
快速排序

问题一:准备一个变量,表示小于等于区域的右边界,如果当前数小于等于num,则把当前数和区域下一个数做交换,区域往右扩一个位置,当前数跳下一个。若当前数大于num,那么跳下一个数即可。
问题二:和问题一类似,两个区域,一个为小于区域的右边界i,一个为大于区域的左边界j,两个变量。当前数小于num,当前数和i数交换,i++,当前数跳下一个。当前数等于num,直接跳下一个。当前数大于num,当前数和j数交换,j--,当前数不动。
那么快速排序,就是以数组内最后一个数作为num,重复上述问题二,最后将大于区域第一个数与最后一个数交换,递归进行即可。
时间复杂度O(N^2)
但如果选取num是随机的,选出来与最后一个数交换然后做划分,可以避免出现最坏情况。
时间复杂度O(NlogN)
相关文章:
算法笔记(二)—— 认识N(logN)的排序算法
递归行为的时间复杂度估算 整个递归过程是一棵多叉树,递归过程相当于利用栈做了一次后序遍历。 对于master公式,T(N)表明母问题的规模为N,T(N/b)表明每次子问题的规模,a为调用次数,加号后面表明,除去调用之…...
最长湍流子数组——滚动窗口,双指针,暴力求解
978. 最长湍流子数组难度中等216收藏分享切换为英文接收动态反馈给定一个整数数组 arr ,返回 arr 的 最大湍流子数组的长度 。如果比较符号在子数组中的每个相邻元素对之间翻转,则该子数组是 湍流子数组 。更正式地来说,当 arr 的子数组 A[i]…...
45.在ROS中实现global planner(1)
前文move_base介绍(4)简单介绍move_base的全局路径规划配置,接下来我们自己实现一个全局的路径规划 1. move_base规划配置 ROS1的move_base可以配置选取不同的global planner和local planner, 默认move_base.cpp#L70中可以看到是…...
Java中导入、导出Excel——HSSFWorkbook 使用
一、介绍 当前B/S模式已成为应用开发的主流,而在企业办公系统中,常常有客户这样子要求:你要把我们的报表直接用Excel打开(电信系统、银行系统)。或者是:我们已经习惯用Excel打印。这样在我们实际的开发中,很多时候需要…...
c#数据结构-列表
列表 数组可以管理大量数组,但缺点是无法更变容量。 创建小了不够用,创建大了浪费空间。 无法预测需要多少大小的时候,可能范围越大,就会浪费越多的空间。 所以,你可能会想要一种可以扩容的东西,代替数组…...
Sa-Token实现分布式登录鉴权(Redis集成 前后端分离)
文章目录1. Sa-Token 介绍2. 登录认证2.1 登录与注销2.2 会话查询2.3 Token 查询3. 权限认证3.1 获取当前账号权限码集合3.2 权限校验3.3 角色校验4. 前后台分离(无Cookie模式)5. Sa-Token 集成 Redis6. SpringBoot 集成 Sa-Token6.1 创建项目6.2 添加依…...
leaflet显示高程
很多地图软件都能随鼠标移动动态显示高程。这里介绍一种方法,我所得出的。1 下载高程数据一般有12.5m数据下载,可惜精度根本不够,比如mapbox的免费在线的,或者91卫图提供百度网盘打包下载的,没法用,差距太大…...
电子学会2022年12月青少年软件编程(图形化)等级考试试卷(三级)答案解析
目录 一、单选题(共25题,共50分) 二、判断题(共10题,共20分) 三、编程题(共3题,共30分) 青少年软件编程(图形化)等级考试试卷(三级) 一、单选题(共25题,共50分) 1. 默认小猫角色…...
ubuntu 驱动更新后导致无法进入界面
**问题描述: **安装新ubuntu系统后未禁止驱动更新导致无法进入登录界面。 解决办法: 首先在进入BIOS中,修改设置以进行命令行操作,然后卸载已有的系统驱动,最后安装新的驱动即可。 开机按F11进入启动菜单栏…...
解决访问GitHub时出现的“您的连接不是私密连接”的问题!
Content问题描述解决办法问题描述 访问github出现您的连接不是私密连接问题,无法正常访问,如下图所示: 解决办法 修改hosts文件。hosts文件位于:C:\Windows\System32\drivers\etc\hosts 首先在https://www.ipaddress.com/查找两…...
初识数据仓库
一、什么是数据仓库数据库 --> OLTP:(on-line transaction processing)翻译为联机事务处理记录某类业务事件的发生,如购买行为,银行交易行为,当行为产生后,系统会记录是谁在何时何地做了何事…...
FilenameUtils工具类部分源码自研
FilenameUtils工具类部分源码自研getExtension(orgFileName)源码如下逐行分析getExtension(orgFileName)源码如下 public class FilenameUtils {public static int indexOfExtension(String fileName) throws IllegalArgumentException {if (fileName null) {return -1;} els…...
【前端领域】3D旋转超美相册(HTML+CSS)
世界上总有一半人不理解另一半人的快乐。 ——《爱玛》 目录 一、前言 二、本期作品介绍 3D旋转相册 三、效果展示 四、详细介绍 五、编码实现 index.html style.css img 六、获取源码 公众号获取源码 获取源码?私信?关注?点赞&…...
Java——聊聊JUC中的原子变量类
文章目录: 1.什么是原子变量类? 2.AtomicInteger(基本类型原子变量类) 3.AtomicIntegerArray(数组类型原子变量类) 4.AtomicMarkableReference(引用类型原子变量类) 5.AtomicInteger…...
elasticsearch索引与搜索初步
ES支持cURL交互,使用http请求完成索引和搜索操作,最基本的格式如下:创建索引我们可以使用PUT方法创建索引,通过指定“索引”、“类型”、“文档ID”锁定文档,通过参数指定文档的数据。红色部分的路由分别指定了“索引”…...
【Python】多线程与多进程学习笔记
本文是一篇学习笔记,学习内容主要来源于莫凡python的文档:https://mofanpy.com/tutorials/python-basic/threading/thread 多线程 线程基本结构 开启子线程的简单方式如下: import threadingdef thread_job():print(This is a thread of %…...
MySQL基础知识点
1.在Linux上安装好MySQL8.0之后,默认数据目录的具体位置是什么?该目录下都保存哪些数据库组件?在目录/usr/sbin、/usr/bin、/etc、/var/log 分别保存哪些组件? 答:默认数据目录:/var/lib/mysql。保存有mysq…...
代码随想录算法训练营第五十九天| 583. 两个字符串的删除操作、72. 编辑距离
Leetcode - 583dp[i][j]代表以i-1结尾的words1的子串 要变成以j-1结尾的words2的子串所需要的次数。初始化: "" 变成"" 所需0次 dp[0][0] 0, ""变成words2的子串 需要子串的长度的次数,所以dp[0][j] j, 同理,dp[i][0] …...
指针引用字符串问题(详解)
通过指针引用字符串可以更加方便灵活的使用字符串。 字符串的引用方式有两种,下面简单介绍一下这两种方法。 1.用字符数组来存放一个字符串。 1.1 可以通过数组名和下标来引用字符串中的一个字符。 1.2 还可以通过数组名和格式声明符%s输出整个字符串。 具体实…...
数据结构——哈夫曼树编程,输入权值实现流程图代码
一、须知 本代码是在数据结构——哈夫曼树编程上建立的,使用时需将代码剪切到C等软件中。需要输入权值方可实现流程图,但是还需要按照编程换算出的结果自己用笔画出流程图。 下面将代码粘贴到文章中,同时举一个例子:二、代…...
网络六边形受到攻击
大家读完觉得有帮助记得关注和点赞!!! 抽象 现代智能交通系统 (ITS) 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 (…...
C++_核心编程_多态案例二-制作饮品
#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为:煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例,提供抽象制作饮品基类,提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...
微信小程序之bind和catch
这两个呢,都是绑定事件用的,具体使用有些小区别。 官方文档: 事件冒泡处理不同 bind:绑定的事件会向上冒泡,即触发当前组件的事件后,还会继续触发父组件的相同事件。例如,有一个子视图绑定了b…...
Xshell远程连接Kali(默认 | 私钥)Note版
前言:xshell远程连接,私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...
AI Agent与Agentic AI:原理、应用、挑战与未来展望
文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例:使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例:使用OpenAI GPT-3进…...
江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命
在华东塑料包装行业面临限塑令深度调整的背景下,江苏艾立泰以一场跨国资源接力的创新实践,重新定义了绿色供应链的边界。 跨国回收网络:废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点,将海外废弃包装箱通过标准…...
JDK 17 新特性
#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持,不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的ÿ…...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...
图表类系列各种样式PPT模版分享
图标图表系列PPT模版,柱状图PPT模版,线状图PPT模版,折线图PPT模版,饼状图PPT模版,雷达图PPT模版,树状图PPT模版 图表类系列各种样式PPT模版分享:图表系列PPT模板https://pan.quark.cn/s/20d40aa…...
Fabric V2.5 通用溯源系统——增加图片上传与下载功能
fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...
