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

排序算法与复杂度介绍

1. 排序算法

1.1 排序算法介绍

排序也成排序算法(Sort Algorithm),排序是将一组数据,依照指定的顺序进行排序的过程

1.2 排序的分类

1、内部排序:
指将需要处理的所有数据都加载到**内部存储器(内存)中进行排序。
2、外部排序
数据量过大,无法全部加载到内存中,需要借助
外部存储(文件等)**进行排序
3、常见的排序算法分类:在这里插入图片描述
4、算法时间复杂度
度量一个程序(算法)执行时间的两种方法
(1)事后统计的方法
这种方法可行,但是有两个问题:一是想对设计的算法的运行性能进行评测,需要实际运行该程序;二是所得时间的统计量依赖于计算机的硬件、软件等环境因素,这种方式,要在同一个计算机的相同状态下运行,才能比较哪个算法速度更快。
(2)事前估算的方法
通过分析某个算法的时间复杂度来判断哪个算法更优。

1.3 算法的时间复杂度

1、时间频度:一个算法执行的时间与算法中语句执行的次数成正比,哪个算法中语句执行次数多,它花费的时间就多。一个算法中语句执行次数称为语句频度或者时间频度,记为T(n)
2、举例说明—基本案例
比如计算1-100所有数字之和,我们设计两种算法

int total = 0 ;
int end = 100 ;
// 使用for循环计算
for(int i = 1; i < end; i++) {total += i;
}
T(n) = n + 1;// 直接计算
total = (1+end) * end/2
T(n) = 1;

3、时间复杂度
1、一般情况下算法中的基本操作语句的重复执行次数是问题规模n的某个函数,用T(n)表示,若有,某个辅助函数 f(n) ,使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于0的常数,则称f(n)是T(n)的同数量级函数。记作T(n) = O(f(n)),称O(f(n))为算法的渐进时间复杂度,简称时间复杂度。
2、T(n)不同,但是时间复杂度可能相同。如: T(n) = n² + 7n+ 6 与 T(n ) = 3n² + 2n+ 2 他们的T(n)不同,但是时间复杂度相同,都为O(n²)。
3、计算时间复杂度的方法:
用常数1 代替运行时间中的所有加法常数 T(n) = n² + 7n+ 6 → T(n) = n² + 7n+ 1
修改后的运行次数函数中,只保留最高阶项 T(n) = n² + 7n+ 1 → T(n) = n²
去除最高阶项的系数 T(n) = n² → T(n) = n² → O(n²)

1.4 常见的时间复杂度

1、常数阶 O(1)

int i = 1;
int j = 2;
++i;
j++;
int m = i + j;

2、对数阶 O(㏒2n)

int i = 1;
while (i < n) {
i = i * 2;
}

3、线性阶 O(n)

for(int i = 0; i <= n; i++) {j = i;j++ ;
}

4、线性对数阶O(n㏒2n)

for( m = 1; m < n; m++) {i = 1;while (i<n) {i = i * 2;}
}

5、平方阶 O(n²)

for(x=1; x<n; x++) {for(i=1; i<n; i++) {j = i;j++;}
}

6、立方阶 O(n³)
7、k次方阶 O(n∧k)
参考上面的O(n²)去理解就好了,O(n³) 相当于3层n循环,其他的类似
8、指数阶 O(2∧n)
说明:
1、 常见的算法时间复杂度由小到大依次为: O(1) < O(㏒2n) < O(n) < O(n㏒2n) < O(n²) < O(n³) < O(n∧k) < O(2∧n),随着问题规模n的不断增大,算法的执行效率越低
2、我们应该尽可能避免使用指数阶的算法

1.5 平均时间复杂度和最坏时间复杂度

1、平均时间复杂度是指所有的可能的输入实例均以等概率出现的情况下,该算法运行的时间
2、最坏情况下的时间复杂度称为最坏时间复杂度。一般讨论的时间复杂度均是最坏情况下的时间复杂度。
3、平均时间复杂度和最坏时间复杂度是否一致,和算法有关。

1.6 算法的空间复杂度简介

基本介绍
1、类似于时间复杂度的讨论,一个算法的空间复杂度(space complexity) 定义为该算法所耗费的存储空间,它也是问题规模n的函数。
2、空间复杂度(space complexity) 是对一个算法在运行过程中临时占用存储空间大小的度量。有的算法需要占用的临时工作单元数与解决问题的规模n有关,它随着n的增大而增大,当n较大时,将占用较多的存储单元,例如快速排序和归并排序算法就属于这种情况。
3、在做算法分析时,主要讨论的是时间复杂度。从用户体验上看,更看重程序运行的速度。一些缓存产品(redis、memcache)和算法(基数排序)本质就是用空间换时间。

相关文章:

排序算法与复杂度介绍

1. 排序算法 1.1 排序算法介绍 排序也成排序算法&#xff08;Sort Algorithm&#xff09;&#xff0c;排序是将一组数据&#xff0c;依照指定的顺序进行排序的过程 1.2 排序的分类 1、内部排序&#xff1a; 指将需要处理的所有数据都加载到**内部存储器&#xff08;内存&am…...

Kafka介绍及Go操作kafka详解

文章目录 Kafka介绍及Go操作kafka详解项目背景解决方案面临的问题业界方案ELKELK方案的问题日志收集系统架构设计架构设计组件介绍将学到的技能消息队列的通信模型点对点模式 queue发布/订阅 topicKafka介绍Kafka的架构图工作流程选择partition的原则ACK应答机制Topic和数据日志…...

DAY05 CSS

文章目录 1 CSS选择器(Selectors)8. 后代(包含)选择器9. 直接子代选择器10. 兄弟选择器11. 相邻兄弟选择器12. 属性选择器 2 伪元素3 CSS样式优先级1. 相同选择器不同样式2. 相同选择器相同样式3. 继承现象4. 选择器不同权值的计算 4 CSS中的值和单位1. 颜色表示法2. 尺寸表示法…...

HTTPS 的加密过程 详解

HTTP 由于是明文传输&#xff0c;所以安全上存在以下三个风险&#xff1a; 窃听风险&#xff0c;比如通信链路上可以获取通信内容。篡改风险&#xff0c;比如通信内容被篡改。冒充风险&#xff0c;比如冒充网站。 HTTPS 在 HTTP 与 TCP 层之间加入了 SSL/TLS 协议&#xff0c…...

spring整合mybatis,junit纯注解开发(包括连接druid报错的所有解决方法)

目录 Spring整合mybatis开发步骤 第一步&#xff1a;创建我们的数据表 第二步&#xff1a;编写对应的实体类 第三步&#xff1a;在pom.xml中导入我们所需要的坐标 spring所依赖的坐标 mybatis所依赖的坐标 druid数据源坐标 数据库驱动依赖 第四步&#xff1a;编写SpringC…...

ClusterIP、NodePort、LoadBalancer 和 ExternalName

Service 定义 在 Kubernetes 中&#xff0c;由于Pod 是有生命周期的&#xff0c;如果 Pod 重启它的 IP 可能会发生变化以及升级的时候会重建 Pod&#xff0c;我们需要 Service 服务去动态的关联这些 Pod 的 IP 和端口&#xff0c;从而使我们前端用户访问不受后端变更的干扰。 …...

【Day1415】Bean管理、SpringBoot 原理、总结、Maven 高级

0 SpringBoot 配置优先级 从上到下 虽然 springboot 支持多种格式配置文件&#xff0c;但是在项目开发时&#xff0c;推荐统一使用一种格式的配置 &#xff08;yml是主流&#xff09; 1 Bean管理 1.1 从 IOC 容器中获取 Bean 1.2 Bean 作品域 可以通过注解 Scope("proto…...

Git之repo sync -c与repo sync -dc用法区别(四十八)

简介&#xff1a; CSDN博客专家&#xff0c;专注Android/Linux系统&#xff0c;分享多mic语音方案、音视频、编解码等技术&#xff0c;与大家一起成长&#xff01; 优质专栏&#xff1a;Audio工程师进阶系列【原创干货持续更新中……】&#x1f680; 优质专栏&#xff1a;多媒…...

vite + vue3 + uniapp 项目从零搭建

vite + vue3 + uniapp 项目从零搭建 1、创建项目1.1、创建Vue3/vite版Uniapp项目1.2、安装依赖1.3、运行项目2、弹出 用户隐私保护提示 方法2.1、更新用户隐私保护指引 和 修改配置文件2.2、授权结果处理方法3、修改`App.vue`文件内容4、处理报`[plugin:uni:mp-using-component…...

在CentOS中配置三个节点之间相互SSH免密登陆

在CentOS中配置三个节点&#xff08;假设分别为node1、node2、node3&#xff09;两两之间相互SSH免密登陆&#xff0c;可以按照以下步骤进行&#xff1a; 一、生成密钥对 在所有节点上生成密钥对&#xff1a; 在每个节点&#xff08;node1、node2、node3&#xff09;上执行以…...

arm 内联汇编基础

一、 Arm架构寄存器体系熟悉 基于arm neon 实现的代码有 intrinsic 和inline assembly 两种实现。 1.1 通用寄存器 arm v7 有 16 个 32-bit 通用寄存器&#xff0c;用 r0-r15 表示。 arm v8 有 31 个 64-bit 通用寄存器&#xff0c;用 x0-x30 表示&#xff0c;和 v7 不一样…...

Java语言程序设计——篇五(1)

数组 概述数组定义实例展示实战演练 二维数组定义数组元素的使用数组初始化器实战演练&#xff1a;矩阵计算 &#x1f4ab;不规则二维数组实战演练&#xff1a;杨辉三角形 概述 ⚡️数组是相同数据类型的元素集合。各元素是有先后顺序的&#xff0c;它们在内存中按照这个先后顺…...

【香橙派开发板测试】:在黑科技Orange Pi AIpro部署YOLOv8深度学习纤维分割检测模型

文章目录 &#x1f680;&#x1f680;&#x1f680;前言一、1️⃣ Orange Pi AIpro开发板相关介绍1.1 &#x1f393; 核心配置1.2 ✨开发板接口详情图1.3 ⭐️开箱展示 二、2️⃣配置开发板详细教程2.1 &#x1f393; 烧录镜像系统2.2 ✨配置网络2.3 ⭐️使用SSH连接主板 三、…...

集成学习在数学建模中的应用

集成学习在数学建模中的应用 一、集成学习概述&#xff08;一&#xff09;基知&#xff08;二&#xff09;相关术语&#xff08;三&#xff09;集成学习为何能提高性能&#xff1f;&#xff08;四&#xff09;集成学习方法 二、Bagging方法&#xff08;一&#xff09;装袋&…...

WebKit 的 Web SQL 数据库:现代浏览器的本地存储解决方案

WebKit 的 Web SQL 数据库&#xff1a;现代浏览器的本地存储解决方案 随着Web应用的不断发展&#xff0c;对本地存储的需求也日益增加。WebKit作为许多现代浏览器的核心引擎&#xff0c;提供了一种强大的本地存储解决方案&#xff1a;Web SQL 数据库。本文将详细探讨Web SQL 数…...

Yolo-World网络模型结构及原理分析(三)——RepVL-PAN

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言1. 网络结构2. 特征融合3. 文本引导&#xff08;Text-guided&#xff09;4. 图像池化注意力&#xff08;Image-Pooling Attention&#xff09;5. 区域文本匹配&…...

代码随想录——一和零(Leetcode474)

题目链接 0-1背包 class Solution {public int findMaxForm(String[] strs, int m, int n) {// 本题m&#xff0c;n为背包两个维度// dp[i][j]:最多右i个0和j个1的strs的最大子集大小int[][] dp new int[m 1][n 1];// 遍历strs中字符串for(String str : strs){int num0 …...

力扣题解(组合总和IV)

377. 组合总和 Ⅳ 给你一个由 不同 整数组成的数组 nums &#xff0c;和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。 题目数据保证答案符合 32 位整数范围。 思路&#xff1a; 本题实质上是给一些数字&#xff0c;让他们在满足和是targ…...

Postgresql主键自增的方法

Postgresql主键自增的方法 一.方法&#xff08;一&#xff09; 使用 serial PRIMARY KEY 插入数据 二.方法&#xff08;二&#xff09; &#x1f388;边走、边悟&#x1f388;迟早会好 一.方法&#xff08;一&#xff09; 使用 serial PRIMARY KEY 建表语句如下&#xf…...

【源码阅读】Sony的go breaker熔断器源码探究

文章目录 背景源码分析总结 背景 在微服务时代&#xff0c;服务和服务之间调用、跨部门调用都是很常见的事&#xff0c;但这些调用都存在很多不确定因素&#xff0c;如核心服务A依赖的部门B服务挂掉了&#xff0c;那么A本身的功能将会受到直接的影响&#xff0c;而这些都会影响…...

边缘计算医疗风险自查APP开发方案

核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

FFmpeg 低延迟同屏方案

引言 在实时互动需求激增的当下&#xff0c;无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作&#xff0c;还是游戏直播的画面实时传输&#xff0c;低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架&#xff0c;凭借其灵活的编解码、数据…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

基于Docker Compose部署Java微服务项目

一. 创建根项目 根项目&#xff08;父项目&#xff09;主要用于依赖管理 一些需要注意的点&#xff1a; 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件&#xff0c;否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

Java + Spring Boot + Mybatis 实现批量插入

在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法&#xff1a;使用 MyBatis 的 <foreach> 标签和批处理模式&#xff08;ExecutorType.BATCH&#xff09;。 方法一&#xff1a;使用 XML 的 <foreach> 标签&#xff…...

Java毕业设计:WML信息查询与后端信息发布系统开发

JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发&#xff0c;实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构&#xff0c;服务器端使用Java Servlet处理请求&#xff0c;数据库采用MySQL存储信息&#xff0…...

[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】

大家好&#xff0c;我是java1234_小锋老师&#xff0c;看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】&#xff0c;分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...

Linux nano命令的基本使用

参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时&#xff0c;显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...