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

算法day03 桶排序 数据结构分类 时间复杂度 异或运算

 学数据结构之前 必看_哔哩哔哩_bilibili

1.认识复杂度和简单排序算法_哔哩哔哩_bilibili

桶排序(Bucket sort)------时间复杂度为O(n)的排序方法(一)_多桶排序时间复杂度-CSDN博客

 桶排序

        测试场景:数组中有10000个随机数,范围在(0-100000)

        使用100个桶,每个桶存放的数据范围为:0-999, 1000-1999, 2000-2999,依次类推

public class BucketSort {public static void bucketSort(int[] data){//新建100个桶int bucketSize = 100;ArrayList<ArrayList<Integer>> buckets = new ArrayList<>(bucketSize);for (int i = 0; i < bucketSize; i++) {buckets.add(new ArrayList<>());  //0-99}//遍历数据,将数据放到桶中for (int i : data) {  //0-10000buckets.get(i / 1000).add(i);}//在桶内部进行排序int k = 0;for (int i = 0; i < bucketSize; i++) {ArrayList<Integer> list = buckets.get(i);Integer[] num = list.toArray(new Integer[1]);Arrays.sort(num);//拷贝到data中for (int n : num) {data[k++] = n;}}}public static void main(String[] args) {Random random = new Random();int[] data = new int[10000];for (int i = 0; i < data.length; i++) {data[i] = random.nextInt(100000);}BucketSort.bucketSort(data);System.out.println(Arrays.toString(data));}}

  



数据结构分类

时间复杂度

        对于有n个元素的数组。

                选择排序:

                        循环一次进行n次比较,找出一个最小值。

                        再循环一次进行n-1次比较找出次小值。

                        。。。

                        这样的循环有n次,每轮循环进行n次,n-1次。。。1次比较

                        时间复杂度计算:

                               循环复杂度:n+n-1+n-2+...+1

                                比较复杂度:n+n-1+n-2+...+1

                                合计为一个等差数列  an^2+bn+C

                                用极限的思维,时间复杂度考虑最坏情况,只看最高项。时间复杂度为o(n^2)

                冒泡排序:

                        假设排序规则为升序

                        从左往右进行一次循环,相邻两个数进行比较交换位置。进行了n-1次比较。第一次循环肯定确定了最右边一个元素。

                        再循环一次进行n-2次确定次右边一个元素。

                        。。。

                        这样的循环有n次,每轮循环进行n-1次,n-2次。。。1次比较

                        时间复杂度计算:

                               循环复杂度:n-1+n-2+...+1

                                比较复杂度:n-1+n-2+...+1

                                合计为一个等差数列  an^2+bn+C

                                用极限的思维,时间复杂度考虑最坏情况,只看最高项。时间复杂度为o(n^2)

异或运算  无进位相加

        两数相加

                      异或运算相比用直接相加的方式来说是没有用到第三个临时参数来储存值,并且位运算是直接操作内存地址,比加减乘除都要快。

                      前提条件是a,b不能是同一个内存地址,而不是说a,b值相等就不能进行位运算相加。因为a,b同内存的话,操作a或者b同时改变了两者的值都归零了。

                      int a,b;          

                      a = a^b

                      b = a^b

                      a = a^b

相关文章:

算法day03 桶排序 数据结构分类 时间复杂度 异或运算

学数据结构之前 必看_哔哩哔哩_bilibili 1.认识复杂度和简单排序算法_哔哩哔哩_bilibili 桶排序&#xff08;Bucket sort&#xff09;------时间复杂度为O(n)的排序方法&#xff08;一&#xff09;_多桶排序时间复杂度-CSDN博客 桶排序 测试场景&#xff1a;数组中有10000个随…...

k8s学习之cobra命令库学习

1.前言 打开k8s代码的时候&#xff0c;我发现基本上那几个核心服务都是使用cobra库作为命令行处理的能力。因此&#xff0c;为了对代码之后的代码学习的有比较深入的理解&#xff0c;因此先基于这个库写个demo&#xff0c;加深对这个库的一些理解吧 2.cobra库的基本简介 Git…...

Spring框架的学习SpringMVC(1)

1.什么是MVC (1)MVC其实就是软件架构的一种设计模式&#xff0c;它将软件的系统分为&#xff0c;&#xff08;视图&#xff0c;模型&#xff0c;控制器&#xff09;三个部分 1.1View(视图) 视图也就是&#xff0c;在浏览器显示的那一个部分&#xff0c;是后端数据的呈现 1.…...

赋值运算符重载和const成员函数和 const函数

文章目录 1.运算符重载(1)(2)运算符重载的语法&#xff1a;(3)运算符重载的注意事项&#xff1a;(4)前置和后置重载区别 2.const成员函数3.取地址及const取地址操作符重载4.总结 1.运算符重载 (1) 我们知道内置类型(整形&#xff0c;字符型&#xff0c;浮点型…)可以进行一系…...

VSCode设置字体大小

方法1&#xff1a;Ctrl 和 Ctrl -&#xff0c;可以控制整个VSCode界面的整体缩放&#xff0c;但是不会调整字体大小 方法2&#xff1a;该方法只能设置编辑器界面的字号&#xff0c;无法改变窗口界面的字号。 &#xff08;1&#xff09;点开左下角如下图标&#xff0c;进入…...

Excel中按列的首行字母顺序,重新排列(VBA脚本)

排序前 要求对4列数据按照第一行abcd的顺序排列 VB脚本如下&#xff1a; 要使用这个脚本&#xff0c;请按照以下步骤操作&#xff1a; 打开Excel&#xff0c;然后按下 Alt F11 打开VBA编辑器。在VBA编辑器中&#xff0c;选择“插入” > “模块”&#xff0c;在打开的模块…...

多线程爬虫技术详解

&#x1f380;引言❤❤ 在当今信息爆炸的时代&#xff0c;网络爬虫&#xff08;Web Crawler&#xff09;作为一种自动获取网页内容的程序&#xff0c;已经成为数据挖掘和信息检索不可或缺的工具。多线程爬虫作为提高爬虫效率的重要手段&#xff0c;通过并行处理技术大幅度提升…...

项目一单机安装基于LNMP结构的WordPress网站 web与数据库服务分离

网站的类型&#xff1a; Jave:LNMT PHP:LNMP Python: LNMU 项目部署&#xff1a; 1.项目的类型&#xff08;项目的开发语言&#xff09; 2.项目运营平台的技术选择 3.尽快让项目运行起来 all in one部署 4. 架构的优化 配置ansible管理环境 配置nginx 配置数据库服务…...

vue事件处理v-on或@

事件处理v-on或 我们可以使用v-on指令&#xff08;简写&#xff09;来监听DOM事件&#xff0c;并在事件触发时执行对应的Javascript。用法&#xff1a;v-on:click"methodName"或click"hander" 事件处理器的值可以是&#xff1a; 内敛事件处理器&#xff1…...

使用OpenCV与PySide(PyQt)的视觉检测小项目练习

OpenCV 提供了丰富的图像处理和计算机视觉功能&#xff0c;可以实现各种复杂的图像处理任务&#xff0c;如目标检测、人脸识别、图像分割等。 PyQt(或PySide)是一个创建GUI应用程序的工具包&#xff0c;它是Python编程语言和Qt库的成功融合。Qt库是最强大的GUI库之一。Qt的快速…...

通信协议_C#实现自定义ModbusRTU主站

背景知识&#xff1a;modbus协议介绍 相关工具 mbslave:充当从站。虚拟串口工具:虚拟出一对串口。VS2022。 实现过程以及Demo 打开虚拟串口工具: 打开mbslave: 此处从站连接COM1口。 Demo实现 创建DLL库&#xff0c;创建ModbusRTU类,进行实现&#xff1a; using Syste…...

【C语言】 —— 编译和链接

【C语言】 —— 编译和链接 一、编译环境和运行环境二、翻译环境2.1、 预处理2.2、 编译&#xff08;1&#xff09;词法分析&#xff08;2&#xff09;语法分析&#xff08;3&#xff09;语义分析 2.3、 汇编2.4、链接 三、运行环境 一、编译环境和运行环境 平时我们说写 C语言…...

DNS正向解析与反向解析实验

正向解析 安装bind软件 [rootlocalhost ~]# dnf install bind bind-utils -y修改主配置文件/etc/named.conf [rootlocalhost ~]# vim /etc/named.conf重启DNS服务&#xff08;named&#xff09; [rootlocalhost ~]# systemctl restart named编辑数据配置文件。在/var/named…...

机器学习简介--NLP(二)

机器学习简介 机器学习简介机器学习例子机器学习分类有监督学习有监督学习的应用 无监督学习 机器学习常见概念数据集k折交叉验证过拟合欠拟合评价指标 机器学习简介 机器学习例子 问题&#xff1a; 2&#xff0c;4&#xff0c;6&#xff0c;8&#xff0c;&#xff1f;&#…...

Winform中使用HttpClient实现调用http的post接口并设置传参content-type为application/json示例

场景 Winform中怎样使用HttpClient调用http的get和post接口并将接口返回json数据解析为实体类&#xff1a; Winform中怎样使用HttpClient调用http的get和post接口并将接口返回json数据解析为实体类_winform解析json-CSDN博客 上面使用HttpClient调用post接口时使用的HttpCon…...

【RAG探索第3讲】LlamaIndex的API调用与本地部署实战

原文链接&#xff1a;【RAG探索第3讲】LlamaIndex的API调用与本地部署实战 今天是2024年7月5日&#xff0c;星期五&#xff0c;天气晴&#xff0c;北京。 RAG的文章也看不少了&#xff0c;今天给大家带来一个llamaindex的实战。分为两个部分&#xff0c;调用ChatGLM的API来用l…...

C# —— 日期对象

DateTime 时间类 存储时间对象 可以获取当前时间 DateTime now DateTime.Now;// 获取当前时间 Console.WriteLine("年:" now.Year);//2023 Console.WriteLine("月:" now.Month);//9 Console.WriteLine("日:" now.Day);//12 Console.WriteLi…...

【MySQL04】【 redo 日志】

文章目录 一、前言二、redo 日志1. redo 日志格式2. Mini-Transaction2.1 以组的形式写入 redo 日志2.2 Mini-Transaction &#xff08;MTR&#xff09;概念 3. redo 日志写入过程3.1 redo 日志缓冲区3.3 redo 日志写入 log buffer 4. redo 日志文件4.1 redo 日志刷盘机制4.2 r…...

Android线性布局的概念与属性

线性布局(LinearLayout)是Android中最简单的布局方式&#xff0c;线性布局方式会使得所有在其内部的控件或子布局按一条水平或垂直的线排列。如图所示&#xff0c;图a是纵向线性布局示意图&#xff0c;图b是横向线性布局示意图。 a&#xff09;纵向线性布局示意图 …...

java反射介绍

Java反射API允许你在运行时检查和修改程序的行为。这意味着你可以动态地创建对象、查看类的字段、方法和构造函数&#xff0c;甚至调用它们。这是一个强大的特性&#xff0c;但也应该谨慎使用&#xff0c;因为它可以破坏封装性。 以下是使用Java反射的一些常见用途&#xff1a;…...

国防科技大学计算机基础课程笔记02信息编码

1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制&#xff0c;因此这个了16进制的数据既可以翻译成为这个机器码&#xff0c;也可以翻译成为这个国标码&#xff0c;所以这个时候很容易会出现这个歧义的情况&#xff1b; 因此&#xff0c;我们的这个国…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

代理篇12|深入理解 Vite中的Proxy接口代理配置

在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...

适应性Java用于现代 API:REST、GraphQL 和事件驱动

在快速发展的软件开发领域&#xff0c;REST、GraphQL 和事件驱动架构等新的 API 标准对于构建可扩展、高效的系统至关重要。Java 在现代 API 方面以其在企业应用中的稳定性而闻名&#xff0c;不断适应这些现代范式的需求。随着不断发展的生态系统&#xff0c;Java 在现代 API 方…...

02.运算符

目录 什么是运算符 算术运算符 1.基本四则运算符 2.增量运算符 3.自增/自减运算符 关系运算符 逻辑运算符 &&&#xff1a;逻辑与 ||&#xff1a;逻辑或 &#xff01;&#xff1a;逻辑非 短路求值 位运算符 按位与&&#xff1a; 按位或 | 按位取反~ …...

倒装芯片凸点成型工艺

UBM&#xff08;Under Bump Metallization&#xff09;与Bump&#xff08;焊球&#xff09;形成工艺流程。我们可以将整张流程图分为三大阶段来理解&#xff1a; &#x1f527; 一、UBM&#xff08;Under Bump Metallization&#xff09;工艺流程&#xff08;黄色区域&#xff…...

Linux入门(十五)安装java安装tomcat安装dotnet安装mysql

安装java yum install java-17-openjdk-devel查找安装地址 update-alternatives --config java设置环境变量 vi /etc/profile #在文档后面追加 JAVA_HOME"通过查找安装地址命令显示的路径" #注意一定要加$PATH不然路径就只剩下新加的路径了&#xff0c;系统很多命…...