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

常用算法解析:从基础排序到图论应用

一、算法基础与设计原则

算法是计算机解决问题的核心工具,其五大基本特性决定了程序的可靠性:

  1. 有穷性:算法必须能在有限步骤内终止
  2. 确定性:每步操作无歧义
  3. 可行性:可被计算机执行
  4. 输入输出:具备数据交互能力
  5. 优化指标:需兼顾时间/空间复杂度、可读性与健壮性

数据结构与算法的关系如同建筑与设计图,经典公式"数据结构+算法=程序"揭示了二者的依存关系。常用算法描述工具包括流程图、N/S盒图、伪代码等,其中伪代码因兼顾结构严谨与语言灵活性被广泛采用。


二、经典排序算法详解

1. 基础排序三剑客

算法时间复杂度空间复杂度稳定性核心思想
直接插入排序O(n²)O(1)稳定构建有序序列,逐个插入新元素
冒泡排序O(n²)O(1)稳定相邻元素两两比较交换
简单选择排序O(n²)O(1)不稳定每次选择最小元素交换到位

应用场景:小规模数据排序(n<1000),实现简单但效率较低

2. 高效排序算法

快速排序
采用分治策略,选取枢轴元素将序列划分为两个子序列。平均时间复杂度O(nlogn),空间复杂度O(logn),不稳定排序。适合处理大规模随机数据。

归并排序
通过递归分解与合并实现稳定排序,时间复杂度稳定为O(nlogn),但需要O(n)辅助空间。常用于外部排序和大文件处理。

堆排序
利用完全二叉树特性构建大顶堆/小顶堆,时间复杂度O(nlogn),空间复杂度O(1)。适合实时性要求高的场景。

3. 特殊排序方法

希尔排序
改进版插入排序,通过动态间隔分组提升效率。时间复杂度介于O(n)到O(n²),空间复杂度O(1),适用于中等规模数据。

外部排序
采用归并策略处理超大数据,分阶段进行:

  1. 内存分段排序生成归并段
  2. 多路归并形成最终有序文件

三、查找算法全解析

1. 基础查找方法

算法时间复杂度适用结构特点
顺序查找O(n)无序线性表实现简单,效率低
折半查找O(logn)有序顺序表效率高但需预先排序
索引查找O(logn)分块有序结构平衡查找速度与维护成本

2. 高级查找结构

二叉查找树
左子树值<根<右子树,平均查找效率O(logn),但可能退化为链表

B/B+树
多路平衡查找树,广泛用于数据库索引,保证查询稳定性

哈希表
通过哈希函数实现O(1)查找,需处理冲突(开放定址法、链地址法)


四、图论核心算法

1. 最小生成树

Prim算法
贪心策略,逐步扩展生成树,适合稠密图,时间复杂度O(n²)

Kruskal算法
按边权升序选择,适合稀疏图,时间复杂度O(eloge)

2. 拓扑排序

AOV网应用:

  1. 选择入度0顶点输出
  2. 删除顶点及关联边
  3. 循环至无顶点剩余
    用于检测工程可行性、课程安排等场景

3. 最短路径

Dijkstra算法
单源最短路径,采用优先队列优化可达O((n+e)logn),不适用负权边

Floyd算法
多源最短路径,动态规划思想,时间复杂度O(n³)


五、递归与分治策略

递归通过自相似结构分解问题,典型应用包括:

  • 阶乘计算
  • 斐波那契数列
  • 汉诺塔问题
  • 树/图的遍历

实现要点

  1. 基线条件确定递归终止
  2. 递归调用缩小问题规模
  3. 栈空间管理防止溢出

算法选择指南

场景特征推荐算法
小规模无序数据插入/冒泡排序
内存受限大规模数据堆排序
需要稳定排序归并排序
快速查询无需预处理哈希表
动态数据集合平衡二叉搜索树
网络路径规划Dijkstra/Floyd算法

理解算法原理与适用场景,结合具体问题的时间空间约束,才能做出最优选择。算法优化永无止境,随着硬件发展与问题演化,经典算法也在持续进化中。

相关文章:

常用算法解析:从基础排序到图论应用

一、算法基础与设计原则 算法是计算机解决问题的核心工具&#xff0c;其五大基本特性决定了程序的可靠性&#xff1a; 有穷性&#xff1a;算法必须能在有限步骤内终止确定性&#xff1a;每步操作无歧义可行性&#xff1a;可被计算机执行输入输出&#xff1a;具备数据交互能力…...

Java Web项目(一)

框架 java web项目总工分为两部分&#xff1a;客户端&#xff08;前端&#xff09;和服务端&#xff08;后端&#xff09; 客户端发起请求&#xff0c;服务端接受请求并进行处理 发起请求的方式&#xff1a;from表单、jQuery ajax from表单 造成全局的变化&#xff0c;在发…...

兴达易控DP主站网关数据映射快速配置案例

兴达易控DP主站网关数据映射快速配置案例 在工业自动化的领域&#xff0c;不同通讯协议之间的转换是常见的需求。特别是Profibus DP与Modbus-RTU这两种广泛应用于不同系统和设备的通讯协议&#xff0c;它们之间的数据转换显得尤为重要。本文将详细探讨兴达易控Profibus DP主站…...

Tailwindcss 入门 v4.1

以 react 为例&#xff0c;步骤如下&#xff1a; npm create vitelatest my-app -- --template react 选择 React 和 JavaScript 根据上述命令的输出提示&#xff0c;运行以下命令 cd my-app npm install npm run dev 一个 React App 初始化完成。 安装 Tailwindcss theme …...

通过 WebSocket 接收和播放 WSS 协议视频流

1.创建wss协议视频 1.1必备包 npm install ws ffmpeg-installer/ffmpeg fluent-ffmpeg 说明&#xff1a;安装以下三个包。 1.2代码实现 说明&#xff1a;创建WebSocket服务器&#xff0c;端口为8080 import { WebSocket, WebSocketServer } from ws; // 导入 WebSocket 和 W…...

HTML 如何改变字体颜色?深入解析与实践指南

网页上的字体颜色是网页设计中至关重要的元素之一&#xff0c;它像字体大小一样&#xff0c;对于提升用户体验起着举足轻重的作用。精心选择和运用字体颜色&#xff0c;能够增强页面的可读性、突出重点信息、营造特定的情感氛围&#xff0c;甚至直接影响用户的视觉感受和品牌认…...

tigase源码学习杂记-组件化设计

前言 tigase官方号称高度抽象和组件化。这篇文章就记录一下我研究组件化的相关设计 概述 我的理解tigase高度组件化是所有的关键的功能的类&#xff0c;它都称之为组件&#xff0c;即只要继承于BasicComponent&#xff0c;它都可以成为组件&#xff0c;BasicComponent类实现…...

十二、人工神经网络及其应用

写在前面 这部分内容老师说很重要,不管是实验还是考试占比都非常大 AIGC的全称是“Artificial Intelligence Generated Content”,即人工智能生成内容。这一术语通常用于指代通过人工智能技术自动生成的各种类型的内容,如文本、图像、音频和视频等。随着AI技术的发展,AIG…...

vscode使用技巧

一、符号定位技巧 ‌跳转到定义‌ F12 或右键「Go to Definition」跳转到符号定义位置‌CtrlClick 直接点击符号跳转&#xff08;支持变量/函数/类&#xff09; ‌符号大纲视图‌ CtrlShiftO 打开文件符号大纲&#xff0c;支持模糊搜索符号名‌输入: 分类显示符号&#xff08;…...

测试基础笔记第七天

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 一、cat命令二、ls -al命令三、>重定向符号四、>>追加重定向符号五、less/more命令六、grep命令七、|管道符八、clear命令九、head命令十、tail命令十一、…...

FOC控制中的正弦PWM和空间矢量PWM对比与理解

参考&#xff1a; simple foc&#xff1a;https://docs.simplefoc.com/docs_chinese/foc_theory博客&#xff1a;https://blog.csdn.net/qq_43332314/article/details/126449398 一、无刷电机基础原理 1.&#xff0c; 原理图&#xff1a;至少三个绕组线圈&#xff08;定子&…...

【Oracle专栏】函数中SQL拼接参数 报错处理

Oracle相关文档,希望互相学习,共同进步 风123456789~-CSDN博客 1.背景 最近同事反馈了一个很奇怪的问题,即有一个函数,入参是当前年月,主要作用是通过SQL语句将不合规的数据插入到指定表中,插入数据时带上入参的年月参数。当前问题:单独测试SQL没有问题可以执行成功,…...

无意间发现的宝藏项目:开源世界中的演示项目精选合集

&#x1f31f;无意间发现的宝藏项目&#xff1a;开源世界中的演示项目精选合集 最近在 GitHub 上随手翻了翻 Spring 官方代码仓库&#xff0c;意外发现一个超有趣的演示项目 —— spring-petclinic。一个轻量但结构完整的 Spring 全家桶演示&#xff0c;让人忍不住一探究竟。 这…...

OpenCSG AutoHub v0.5.0 版本发布

OpenCSG AutoHub v0.5.0 版本发布 作为一款智能化自动化操作的浏览器插件&#xff0c;AutoHub不断致力于为用户提供更加高效、便捷的网页浏览体验。本次 v0.5.0版本 的发布&#xff0c;不仅进一步强化了核心功能&#xff0c;还引入了一些创新特性&#xff0c;旨在帮助用户更智…...

基于Python智能体API的Word自动化排版系统:从零构建全流程模块化工作流与版本控制研究

基于Python智能体API的Word自动化排版系统:从零构建全流程模块化工作流与版本控制实践研究 1. 引言2. 研究背景与意义3. 自动排版工作流的设计原理3.1 文档内容提取与解析3.2 样式参数与格式化规则3.3 智能体API接口调用3.4 自动生成与批量处理3.5 与生成式AI的协同4. 系统架构…...

在 Node.js 中设置响应的 MIME 类型

在 Node.js 中设置响应的 MIME 类型是为了让浏览器正确解析服务器返回的内容&#xff0c;比如 HTML、CSS、图片、JSON 等。我们通常通过设置响应头中的 Content-Type 字段来完成。 ✅ 一、什么是 MIME 类型&#xff08;Content-Type&#xff09;&#xff1f; MIME&#xff08;…...

jsch(shell终端Java版)

学习笔记 Java SSH库使用简介&#xff1a;Apache sshd和JSch&#xff08;Java Secure Channel&#xff09; github - fork of the popular jsch library JSch学习笔记 web-shell - gitee代码 - 纯Java实现一个web shell登录Linux远程主机&#xff0c;技术选型 SpringBoot …...

Redis分布式锁RedLock机制详解

一、RedLock机制解决的问题 核心场景&#xff1a;解决传统Redis单节点/主从架构下分布式锁的不可靠问题。当主节点故障时&#xff0c;若从节点未同步锁信息&#xff0c;可能导致多个客户端同时持有锁&#xff0c;破坏互斥性。 典型问题案例&#xff1a; 主从切换锁丢失&…...

Vivado中Tri_mode_ethernet_mac的时序约束、分析、调整——(五)调试注意的问题

一、几个注意点 1、每个bank中IO的组织形式 1Bank的52Pins分4 Byte Group&#xff0c;每Byte Group 13PinsNibble_up 7Pins Nibble_low 6Pins。 每个nibble一个bitslice_control管理自己的6~7个pins 。 每个pin对应一个bitslice&#xff0c;它内部又包含多个component&#…...

MFC文件-写MP4

下载本文件 本文件将创作MP4视频文件代码整合到两个文件中&#xff08;Mp4Writer.h和Mp4Writer.cpp)&#xff0c;将IYUV视频流&#xff0c;PCM音频流写入MP4文件。本文件仅适用于MFC程序。 使用方法 1.创建MFC项目。 2.将Mp4Writer.h和Mp4Writer.cpp文件复制到项目目录下。 3…...

PyTorch 深度学习实战(39):归一化技术对比(BN/LN/IN/GN)

在上一篇文章中&#xff0c;我们全面解析了注意力机制的发展历程。本文将深入探讨深度学习中的归一化技术&#xff0c;对比分析BatchNorm、LayerNorm、InstanceNorm和GroupNorm四种主流方法&#xff0c;并通过PyTorch实现它们在图像分类和生成任务中的应用效果。 一、归一化技术…...

C#/.NET/.NET Core技术前沿周刊 | 第 35 期(2025年4.14-4.20)

前言 C#/.NET/.NET Core技术前沿周刊&#xff0c;你的每周技术指南针&#xff01;记录、追踪C#/.NET/.NET Core领域、生态的每周最新、最实用、最有价值的技术文章、社区动态、优质项目和学习资源等。让你时刻站在技术前沿&#xff0c;助力技术成长与视野拓宽。 欢迎投稿、推荐…...

柱状图QCPBars

一、QCPBars 概述 QCPBars 是 QCustomPlot 中用于绘制柱状图/条形图的类&#xff0c;支持单组或多组柱状图显示&#xff0c;可自定义宽度、颜色和间距等属性。 二、主要属性 属性类型描述widthdouble柱子的宽度&#xff08;坐标轴单位&#xff09;widthTypeWidthType宽度计算…...

2025-04-20 李沐深度学习4 —— 自动求导

文章目录 1 导数拓展1.1 标量导数1.2 梯度&#xff1a;向量的导数1.3 扩展到矩阵1.4 链式法则 2 自动求导2.1 计算图2.2 正向模式2.3 反向模式 3 实战&#xff1a;自动求导3.1 简单示例3.2 非标量的反向传播3.3 分离计算3.4 Python 控制流 硬件配置&#xff1a; Windows 11Inte…...

Nginx在微服务架构项目(Spring Cloud)中的强大作用

文章目录 一、Nginx是什么&#xff1f;二、Nginx在微服务架构&#xff08;Spring Cloud&#xff09;项目中的作用1.前端静态资源托管2.反向代理后端 API3.负载均衡4.SSL 证书与 HTTPS 支持5.缓存与压缩优化6.安全防护7.灰度发布与流量控制8.跨域处理&#xff08;CORS&#xff0…...

Mysql相关知识2:Mysql隔离级别、MVCC、锁

文章目录 MySQL的隔离级别可重复读的实现原理Mysql锁按锁的粒度分类按锁的使用方式分类按锁的状态分类 MySQL的隔离级别 在 MySQL 中&#xff0c;隔离级别定义了事务之间相互隔离的程度&#xff0c;用于控制一个事务对数据的修改在何时以及如何被其他事务可见。MySQL 支持四种…...

解决IDEA创建SpringBoot项目没有Java版本8

问题&#xff1a;idea2023版本创建springboot的过程中&#xff0c;选择java版本时发现没有java8版本&#xff0c;只有java17和java20 原因&#xff1a;spring2.X版本在2023年11月24日停止维护了&#xff0c;因此创建spring项目时不再有2.X版本的选项&#xff0c;只能从3.1.X版本…...

第十章:Agent 的评估、调试与可观测性:确保可靠与高效

引言 随着我们一步步构建出越来越复杂的 AI Agent&#xff0c;赋予它们高级工具和更智能的策略&#xff0c;一个至关重要的问题浮出水面&#xff1a;我们如何知道这些 Agent 是否真的有效、可靠&#xff1f;当它们行为不符合预期时&#xff0c;我们又该如何诊断和修复问题&…...

8节串联锂离子电池组可重构buck-boost均衡拓扑结构 simulink模型仿真

8节串联锂离子电池组 极具创新性 动态分组均衡策略&#xff0c;支持3种均衡模式 1.最高SOC电池给最低SOC电池均衡 2.高能电池组电池给最低SOC电池均衡 3.高能电池组电池给低能电池组电池均衡 支持手动设置均衡开启阈值和终止阈值 均衡效果非常好...

Oracle EBS COGS Recognition重复生成(一借一贷)

背景 月结用户反馈“发出商品”(实际为递延销货成本)不平,本月都是正常操作月结程序,如正常操作步骤如下: 记录订单管理事务处理 (Record Order Management Transactions)收集收入确认信息 (Collect Revenue Recognition Information)生成销货成本确认事件 (Generate COGS …...

Linux命令--将控制台的输入写入文件

原文网址&#xff1a;Linux命令--将控制台的输入写入文件-CSDN博客 简介 本文介绍Linux将控制台的输入写入文件的方法。 方案1&#xff1a;cat > file1&#xff08;推荐&#xff09; 普通用法 cat > file1 输入结束后&#xff0c;用CtrlD退出。 示例 使用root权限…...

使用BQ76PL455和STM32的SAE电动方程式电动汽车智能BMS

BMS对任何电动汽车来说都是必不可少的&#xff0c;它可以监控电池的行为&#xff0c;确保安全行驶。 该项目旨在降低成本&#xff0c;同时为每个电池模块提供可扩展的BMS。BQ76PL455具有监测6-16个单元的能力&#xff0c;8通道辅助输入(用于温度监测)和多达15个其他ic用于Daisy…...

OpenCV 模板与多个对象匹配方法详解(继OpenCV 模板匹配方法详解)

文章目录 前言1.导入库2.图片预处理3.输出模板图片的宽和高4.模板匹配5.获取匹配结果中所有符合阈值的点的坐标5.1 threshold 0.9&#xff1a;5.2 loc np.where(res > threshold)&#xff1a; 6.遍历所有匹配点6.1 loc 的结构回顾6.2 loc[::-1] 的作用6.2.1 为什么需要反转…...

7.0/Q1,Charls最新文章解读

文章题目&#xff1a;Anti-hypertensive medication adherence, socioeconomic status, and cognitive aging in the Chinese community-dwelling middle-aged and older adults ≥ 45 years: a population-based longitudinal study DOI&#xff1a;10.1186/s12916-025-03949-…...

【第三十二周】CLIP 论文阅读笔记

CLIP 摘要Abstract文章信息引言方法预训练推理Q&A 关键代码实验结果总结 摘要 本篇博客介绍了CLIP&#xff08;Contrastive Language-Image Pre-training&#xff09;&#xff0c;这是OpenAI于2021年提出的多模态预训练模型&#xff0c;其核心思想是通过对比学习将图像与文…...

在 Ubuntu 系统上安装 PostgreSQL

在 Ubuntu 系统上安装 PostgreSQL 的完整指南&#xff1a; 一、安装 PostgreSQL&#xff08;最新版本&#xff09; 1. 更新软件包列表&#xff1a; bash sudo apt update 2. 安装 PostgreSQL 和客户端工具&#xff1a; bash sudo apt install postgresql po…...

【MySQL】数据类型

&#x1f3e0;个人主页&#xff1a;Yui_ &#x1f351;操作环境&#xff1a;Centos7 &#x1f680;所属专栏&#xff1a;MySQL 文章目录 前言1. bit类型2.tinyint类型3. float类型4. decimal5. char类型6. varchar5&6 char和varchar的比较7.日期和时间类型8.enum和set总结 …...

Mac上Cursor无法安装插件解决方法

可能是微软的vscode被cursor这些新晋的AI-IDE白嫖够了&#xff0c;所以现在被制裁了&#xff0c;cursor下载不了vscode插件了。​需要自己修改扩展商店源。 近期微软调整了 API 鉴权策略或限制了非官方客户端的访问权限。 解决方案 一、找到 product.json 文件 打开终端&…...

PI0 Openpi 部署(仅测试虚拟环境)

https://github.com/Physical-Intelligence/openpi/tree/main 我使用4070tisuper, 14900k,完全使用官方默认设置&#xff0c;没有出现其他问题。 目前只对examples/aloha_sim进行测试&#xff0c;使用docker进行部署, 默认使用pi0_aloha_sim模型(但是文档上没找到对应的&…...

NumPy数组和二维列表的区别

在 Python 中&#xff0c;NumPy 数组和二维列表在性能方面存在诸多不同&#xff0c;下面从存储方式、内存占用、操作速度、缓存局部性这几个角度详细分析。 存储方式 二维列表&#xff1a;它是 Python 内置的数据结构&#xff0c;列表中的每个元素实际上是一个引用&#xff0…...

学习设计模式《四》——单例模式

一、基础概念 单例模式的本质【控制实例数目】&#xff1b; 单例模式的定义&#xff1a;是用来保证这个类在运行期间只会被创建一个类实例&#xff1b;单例模式还提供了一个全局唯一访问这个类实例的访问点&#xff08;即GetInstance方法&#xff09;单例模式只关心类实例的创建…...

构建具备推理与反思能力的高级 Prompt:LLM 智能代理设计指南

在构建强大的 AI 系统&#xff0c;尤其是基于大语言模型&#xff08;LLM&#xff09;的智能代理&#xff08;Agent&#xff09;时&#xff0c;Prompt 设计的质量决定了系统的智能程度。传统 Prompt 通常是简单的问答或填空式指令&#xff0c;而高级任务需要更具结构性、策略性和…...

NLP 梳理03 — 停用词删除和规范化

一、说明 前文我们介绍了标点符号删除、文本的大小写统一&#xff0c;本文介绍英文文章的另一些删除内容&#xff0c;停用词删除。还有规范化处理。 二、什么是停用词&#xff0c;为什么删除它们&#xff1f; 2.1 停用词的定义 停用词是语言中的常用词&#xff0c;通常语义…...

算法—插入排序—js(小数据或基本有序数据)

插入排序原理&#xff1a;&#xff08;适合小规模数据&#xff09; 将数组分为“已排序”和“未排序”两部分&#xff0c;逐个将未排序元素插入到已排序部分的正确位置。 特点&#xff1a; 时间复杂度&#xff1a;平均 O(n)&#xff0c;最优&#xff08;已有序&#xff09;O(n…...

家庭电脑隐身后台自动截屏软件,可远程查看

7-4 本文介绍一个小软件&#xff0c;可以在电脑后台运行&#xff0c;并且记录电脑的屏幕画面保存下来&#xff0c;并且可以远程提取查看。 可以用于记录长时间运行的软件的执行画面过程&#xff0c;或者用于记录家庭中小孩使用电脑的过程&#xff0c;如果没有好好上网课&…...

【Agent】AI智能体评测基座AgentCLUE-General

note AgentCLUE-General将题目划分为“联网检索”、“数据分析”、“多模态理解”和“多场景组合”任务AgentCLUE-General为每个题目都提供一个标准答案&#xff0c;将Agent智能体的答案与标准答案进行规则匹配判断对错 文章目录 note一、任务划分和场景划分二、答案提取的pro…...

最新iOS性能测试方法与教程

一、工具instrument介绍 使用Xcode的instrument进行测试&#xff0c;instrument自带了很多性能方面的测试工具&#xff0c;如图所示&#xff1a; 二、常见性能测试内容 不管是安卓还是iOS的性能测试&#xff0c;常见的性能测试都要包含这五个方面&#xff1a; 1、内存&#xff…...

多模态大语言模型arxiv论文略读(三十)

Mastering Text-to-Image Diffusion: Recaptioning, Planning, and Generating with Multimodal LLMs ➡️ 论文标题&#xff1a;Mastering Text-to-Image Diffusion: Recaptioning, Planning, and Generating with Multimodal LLMs ➡️ 论文作者&#xff1a;Ling Yang, Zhao…...

【AI论文】CLIMB:基于聚类的迭代数据混合自举语言模型预训练

摘要&#xff1a;预训练数据集通常是从网络内容中收集的&#xff0c;缺乏固有的领域划分。 例如&#xff0c;像 Common Crawl 这样广泛使用的数据集并不包含明确的领域标签&#xff0c;而手动整理标记数据集&#xff08;如 The Pile&#xff09;则是一项劳动密集型工作。 因此&…...

AI大模型发展现状与MCP协议诞生的技术演进

1. 大模型能力边界与用户痛点&#xff08;2023年&#xff09; 代表模型&#xff1a;GPT-4&#xff08;OpenAI&#xff09;、Claude 3&#xff08;Anthropic&#xff09;、通义千问&#xff08;阿里云&#xff09;等展现出强大的生成能力&#xff0c;但存在明显局限&#xff1a…...