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

数据结构和算法专题---2、算法思想

上文讲到算法的概念、复杂度,本文给大家介绍具体的算法思想,让大家对算法设计理念有个认识,后续再分别介绍各种算法。

算法思想

算法是解决问题的一种思想和方法,其基本思想是将一个复杂问题分解为多个简单的子问题,然后通过一定的逻辑和操作方法将这些子问题的解组合成原问题的解。

分而治之

把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题,直到最后子问题小到可以简单的直接求解,原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础,如排序算法(快速排序,归并排序),傅立叶变换(快速傅立叶变换),大数据中的MR,现实中如汉诺塔游戏。

分治法对问题有一定的要求:

  • 该问题缩小到一定程度后,就可以轻松解决
  • 问题具有可拆解性,不是一团无法拆分的乱麻
  • 拆解后的答案具有可合并性。能组装成最终结果
  • 拆解的子问题要相互独立,互相之间不存在或者很少有依赖关系

动态规划

基本思想与分治法类似,也是将待求解的问题分解为若干个子问题(阶段),按顺序求解子阶段,前一子问题的解,为后一子问题的求解提供了有用的信息。在求解任一子问题时,列出各种可能的局部解,通过决策保留那些有可能达到最优的局部解,丢弃其他。依次解决各子问题,最后一个子问题就是初始问题的解。

与分治法最大的不同在于,分治法的思想是并发,动态规划的思想是分步。该方法经分解后得到的子问题往往不是互相独立的,其下一个子阶段的求解往往是建立在上一个子阶段的解的基础上。动态规划算法同样有一定的适用性场景要求:

  • 最优化解:拆解后的子阶段具备最优化解,且该最优化解与追踪答案方向一致
  • 流程向前,无后效性:上一阶段的解决方案一旦确定,状态就确定,只会影响下一步,而不会反向影响
  • 阶段关联:上下阶段不是独立的,上一阶段会对下一阶段的行动提供决策性指导。这不是必须的,但是如果具备该特征,动态规划算法的意义才能更大的得到体现

贪心算法

同样对问题要求作出拆解,但是每一步,以当前局部为目标,求得该局部的最优解。那么最终问题解决时,得到完整的最优解。也就是说,在对问题求解时,总是做出在当前看来是最好的选择,而不去从整体最优上加以考虑。从这一角度来讲,该算法具有一定的场景局限性。

  • 要求问题可拆解,并且拆解后每一步的状态无后效性(与动态规划算法类似)
  • 要求问题每一步的局部最优,与整体最优解方向一致。至少会导向正确的主方向。

回溯算法

回溯算法实际上是一个类似枚举的搜索尝试过程,在每一步的问题下,列举可能的解决方式。选择某个方案往深度探究,寻找问题的解,当发现已不满足求解条件,或深度达到一定数量时,就返回,尝试别的路径。回溯法一般适用于比较复杂的,规模较大的问题。有“通用解题法”之称。

  • 问题的解决方案具备可列举性,数量有限
  • 界定回溯点的深度。达到一定程度后,折返

分支限界

与回溯法类似,也是一种在空间上枚举寻找最优解的方式。但是回溯法策略为深度优先。分支法为广度优先。分支法一般找到所有相邻结点,先采取淘汰策略,抛弃不满足约束条件的结点,其余结点加入活结点表。然后从存活表中选择一个结点作为下一个操作对象

相关文章:

数据结构和算法专题---2、算法思想

上文讲到算法的概念、复杂度,本文给大家介绍具体的算法思想,让大家对算法设计理念有个认识,后续再分别介绍各种算法。 算法思想 算法是解决问题的一种思想和方法,其基本思想是将一个复杂问题分解为多个简单的子问题,…...

在AWS Lambda上部署标准FFmpeg工具——自定义层的方案

大纲 1 确定Lambda运行时环境1.1 Lambda系统、镜像、内核版本1.2 运行时1.2.1 Python1.2.2 Java 2 打包FFmpeg3 创建Lambda的Layer4 测试4.1 创建Lambda函数4.2 附加FFmpeg层4.3 添加测试代码4.4 运行测试 参考文献 FFmpeg被广泛应用于音/视频流处理领域。对于简单的需求&#…...

prometheus服务发现之consul

文章目录 前言一、Consul 在这里的作用二、原理三、实现过程安装 consul节点信息(exporter)注册进去consul节点信息(exporter)从consul解除注册:prometheus配置consul地址 总结 前言 我们平时使用 prometheus 收集监控…...

基于SSM的鞍山职业技术学院图书借阅管理系统

文章目录 项目介绍主要功能截图:部分代码展示设计总结项目获取方式🍅 作者主页:超级无敌暴龙战士塔塔开 🍅 简介:Java领域优质创作者🏆、 简历模板、学习资料、面试题库【关注我,都给你】 🍅文末获取源码联系🍅 项目介绍 基于SSM的鞍山职业技术学院图书借阅管理…...

分布式数据库HBase

文章目录 前言 一、HBase概述 1.1.1 什么是HBase HBase是一个分布式的、面向列的开源数据库HBase是Google BigTable的开源实现HBase不同于一般的关系数据库, 适合非结构化数据存储HBase是一种分布式、可扩展、支持海量数据存储的 NoSQL数据库。HBase是依赖Hadoop的。为什么HBa…...

快捷切换raw页面到repo页面-Raw2Repo插件

Raw2Repo By Rick 📖快捷切换代码托管平台raw页面到repo页面 🔗github链接 https://github.com/rickhqh/Raw2Repo ✨Features 功能: ✅单击 Raw2Repo 插件按钮,即可跳转到相应的代码仓库页面。✅支持 GitHub、Gitee、GitCode …...

web:[GXYCTF2019]BabyUpload(文件上传、一句话木马、文件过滤)

题目 页面显示为文件上传 随便上传一个文件看看 上传一个文本文件显示 上传了一个图片显示 上传包含一句话木马的图片 上传了一个包含php一句话木马的文件,显示如上 换一个写法 上传成功 尝试上传.htaccess,上传失败,用抓包修改文件后缀 …...

C++ Div3、Sqrt 函数高性能实现(带汇编指令集)

均采用魔法数字(Magic Number)实现,一个是经典求平方根函数所使用的魔法数字:0x5f375a86、0x5f3759df。 float Sqrt(float x) noexcept { /* 0x5f3759df */float xhalf 0.5f * x;int32_t i *(int32_t*)&x;i 0x5f375a86 - …...

西南科技大学模拟电子技术实验四(集成运算放大器的线性应用)预习报告

一、计算/设计过程 说明:本实验是验证性实验,计算预测验证结果。是设计性实验一定要从系统指标计算出元件参数过程,越详细越好。用公式输入法完成相关公式内容,不得贴手写图片。(注意:从抽象公式直接得出结果,不得分,页数可根据内容调整) 反相比例运算电路(1)实验…...

【五分钟】学会利用cv2.resize()函数实现图像缩放

引言 在numpy知识库:深入理解numpy.resize函数和数组的resize方法中,小编较为详细地探讨了numpy的resize函数背后的机理。从结果来看,numpy.resize函数并不适合对图像进行缩放操作。而opencv中的resize函数虽然和numpy的resize函数同名&…...

vuepress-----18、图片缩放

图片引入两种方式 地址 # 图片缩放插件 # 实战 md文件引入图片 <img class"zoom-custom-imgs" :src"$withBase(/favicon.ico)" alt"favicon">安装配置插件 vuepress/medium-zoom: {selector: img.zoom-custom-imgs,},效果展示...

前端开发_移动Web+动画

平面转换 作用&#xff1a;为元素添加动态效果&#xff0c;一般与过渡配合使用 概念&#xff1a;改变盒子在平面内的形态&#xff08;位移、旋转、缩放、倾斜&#xff09; 平面转换又叫 2D 转换 平移 属性&#xff1a;transform: translate(X轴移动距离&#xff0c;Y轴移动…...

【Python】 生成二维码

创建了一个使用 python 创建二维码的程序。 下面是生成的程序的图像。 功能描述 输入网址&#xff08;URL&#xff09;。 输入二维码的名称。 当单击 QR 码生成按钮时&#xff0c;将使用 QRname 中输入的字符将 QR 码生成为图像。 程序代码 import qrcode import tkinterd…...

Qt与Sqlite3

操作流程&#xff1a; (1)与数据库连接 (2)进行增删改查操作 (3)关闭数据库 示例&#xff1a; 参考&#xff1a;Qt 操作SQLite数据库_qt sqlite数据库操作_houxian1103的博客-CSDN博客 再谈QSqlQuery::exec: database not open问题的解决_qt database not open-CSDN博客…...

在idea中使用maven创建dynamic web project

1、先创建一个empty project 2、添加一个module , 核心是选择maven archetype webapp, 这个是maven提供的创建web工程的模版。 3、添加完等自动安装好即可 4、目录可能不完整 右键src---->点击New---->点击Directory &#xff08;注意&#xff1a;这是笔者所缺失的结…...

【外观模式】SpringBoot集成mail发送邮件

前言 发送邮件功能&#xff0c;借鉴 刚果商城&#xff0c;根据文档及项目代码实现。整理总结便有了此文&#xff0c;文章有不对的点&#xff0c;请联系博主指出&#xff0c;请多多点赞收藏&#xff0c;您的支持是我最大的动力~ 发送邮件功能主要借助 mail、freemarker以及rocke…...

GUAVA 工具类

Guava是一个Google的开源Java库&#xff0c;常用的工具&#xff1a; 集合工具类&#xff0c;包括Lists&#xff08;创建&#xff1a;newArrayList、newLinkedList等&#xff09;、Sets&#xff08;创建&#xff1a;newHashSet、newLinkedHashSet等&#xff09;和Maps&#xff…...

高云GW1NSR-4C开发板上手使用

1.开发板 核心板&#xff0c;主芯片GW1NSR-LV4CQN48P&#xff0c;丝印文字“奥陶纪Octet&#xff0c;QQ群808770961”&#xff1a; 晶振&#xff1a;27MHz&#xff0c;22引脚 两个按键&#xff1a;靠近中间&#xff0c;23引脚&#xff0c;按下为低电平&#xff1b;靠近外侧&…...

androidstudio设置内存

androidstudio一直 scanning files to index&#xff0c;需要去设置内存&#xff1a; 操作如下&#xff1a;...

[ 蓝桥杯Web真题 ]-Markdown 文档解析

目录 介绍 准备 目标 规定 思路 补充知识 解法参考 介绍 Markdown 因为其简洁的语法大受欢迎&#xff0c;已经成为大家写博客或文档时必备的技能点&#xff0c;众多博客平台都提倡用户使用 Markdown 语法进行文章书写&#xff0c;然后再发布后&#xff0c;实时的将其转化…...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

大数据零基础学习day1之环境准备和大数据初步理解

学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 &#xff08;1&#xff09;设置网关 打开VMware虚拟机&#xff0c;点击编辑…...

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...

vue3+vite项目中使用.env文件环境变量方法

vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量&#xff0c;这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...

Spring数据访问模块设计

前面我们已经完成了IoC和web模块的设计&#xff0c;聪明的码友立马就知道了&#xff0c;该到数据访问模块了&#xff0c;要不就这俩玩个6啊&#xff0c;查库势在必行&#xff0c;至此&#xff0c;它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据&#xff08;数据库、No…...

是否存在路径(FIFOBB算法)

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

HashMap中的put方法执行流程(流程图)

1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中&#xff0c;其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下&#xff1a; 初始判断与哈希计算&#xff1a; 首先&#xff0c;putVal 方法会检查当前的 table&#xff08;也就…...

C++.OpenGL (20/64)混合(Blending)

混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...

RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)

RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发&#xff0c;后来由Pivotal Software Inc.&#xff08;现为VMware子公司&#xff09;接管。RabbitMQ 是一个开源的消息代理和队列服务器&#xff0c;用 Erlang 语言编写。广泛应用于各种分布…...