排序算法与复杂度介绍
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 排序算法介绍 排序也成排序算法(Sort Algorithm),排序是将一组数据,依照指定的顺序进行排序的过程 1.2 排序的分类 1、内部排序: 指将需要处理的所有数据都加载到**内部存储器(内存&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 由于是明文传输,所以安全上存在以下三个风险: 窃听风险,比如通信链路上可以获取通信内容。篡改风险,比如通信内容被篡改。冒充风险,比如冒充网站。 HTTPS 在 HTTP 与 TCP 层之间加入了 SSL/TLS 协议,…...

spring整合mybatis,junit纯注解开发(包括连接druid报错的所有解决方法)
目录 Spring整合mybatis开发步骤 第一步:创建我们的数据表 第二步:编写对应的实体类 第三步:在pom.xml中导入我们所需要的坐标 spring所依赖的坐标 mybatis所依赖的坐标 druid数据源坐标 数据库驱动依赖 第四步:编写SpringC…...

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

【Day1415】Bean管理、SpringBoot 原理、总结、Maven 高级
0 SpringBoot 配置优先级 从上到下 虽然 springboot 支持多种格式配置文件,但是在项目开发时,推荐统一使用一种格式的配置 (yml是主流) 1 Bean管理 1.1 从 IOC 容器中获取 Bean 1.2 Bean 作品域 可以通过注解 Scope("proto…...

Git之repo sync -c与repo sync -dc用法区别(四十八)
简介: CSDN博客专家,专注Android/Linux系统,分享多mic语音方案、音视频、编解码等技术,与大家一起成长! 优质专栏:Audio工程师进阶系列【原创干货持续更新中……】🚀 优质专栏:多媒…...
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中配置三个节点(假设分别为node1、node2、node3)两两之间相互SSH免密登陆,可以按照以下步骤进行: 一、生成密钥对 在所有节点上生成密钥对: 在每个节点(node1、node2、node3)上执行以…...

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

Java语言程序设计——篇五(1)
数组 概述数组定义实例展示实战演练 二维数组定义数组元素的使用数组初始化器实战演练:矩阵计算 💫不规则二维数组实战演练:杨辉三角形 概述 ⚡️数组是相同数据类型的元素集合。各元素是有先后顺序的,它们在内存中按照这个先后顺…...

【香橙派开发板测试】:在黑科技Orange Pi AIpro部署YOLOv8深度学习纤维分割检测模型
文章目录 🚀🚀🚀前言一、1️⃣ Orange Pi AIpro开发板相关介绍1.1 🎓 核心配置1.2 ✨开发板接口详情图1.3 ⭐️开箱展示 二、2️⃣配置开发板详细教程2.1 🎓 烧录镜像系统2.2 ✨配置网络2.3 ⭐️使用SSH连接主板 三、…...

集成学习在数学建模中的应用
集成学习在数学建模中的应用 一、集成学习概述(一)基知(二)相关术语(三)集成学习为何能提高性能?(四)集成学习方法 二、Bagging方法(一)装袋&…...
WebKit 的 Web SQL 数据库:现代浏览器的本地存储解决方案
WebKit 的 Web SQL 数据库:现代浏览器的本地存储解决方案 随着Web应用的不断发展,对本地存储的需求也日益增加。WebKit作为许多现代浏览器的核心引擎,提供了一种强大的本地存储解决方案:Web SQL 数据库。本文将详细探讨Web SQL 数…...

Yolo-World网络模型结构及原理分析(三)——RepVL-PAN
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言1. 网络结构2. 特征融合3. 文本引导(Text-guided)4. 图像池化注意力(Image-Pooling Attention)5. 区域文本匹配&…...

代码随想录——一和零(Leetcode474)
题目链接 0-1背包 class Solution {public int findMaxForm(String[] strs, int m, int n) {// 本题m,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 ,和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。 题目数据保证答案符合 32 位整数范围。 思路: 本题实质上是给一些数字,让他们在满足和是targ…...

Postgresql主键自增的方法
Postgresql主键自增的方法 一.方法(一) 使用 serial PRIMARY KEY 插入数据 二.方法(二) 🎈边走、边悟🎈迟早会好 一.方法(一) 使用 serial PRIMARY KEY 建表语句如下…...

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

第19节 Node.js Express 框架
Express 是一个为Node.js设计的web开发框架,它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用,和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

测试微信模版消息推送
进入“开发接口管理”--“公众平台测试账号”,无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息: 关注测试号:扫二维码关注测试号。 发送模版消息: import requests da…...
Python爬虫实战:研究feedparser库相关技术
1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...
测试markdown--肇兴
day1: 1、去程:7:04 --11:32高铁 高铁右转上售票大厅2楼,穿过候车厅下一楼,上大巴车 ¥10/人 **2、到达:**12点多到达寨子,买门票,美团/抖音:¥78人 3、中饭&a…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)
引言:为什么 Eureka 依然是存量系统的核心? 尽管 Nacos 等新注册中心崛起,但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制,是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...
VTK如何让部分单位不可见
最近遇到一个需求,需要让一个vtkDataSet中的部分单元不可见,查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行,是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示,主要是最后一个参数,透明度…...

10-Oracle 23 ai Vector Search 概述和参数
一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI,使用客户端或是内部自己搭建集成大模型的终端,加速与大型语言模型(LLM)的结合,同时使用检索增强生成(Retrieval Augmented Generation &#…...

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

搭建DNS域名解析服务器(正向解析资源文件)
正向解析资源文件 1)准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2)服务端安装软件:bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...
Python 训练营打卡 Day 47
注意力热力图可视化 在day 46代码的基础上,对比不同卷积层热力图可视化的结果 import torch import torch.nn as nn import torch.optim as optim from torchvision import datasets, transforms from torch.utils.data import DataLoader import matplotlib.pypl…...