数据结构和算法专题---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+动画
平面转换 作用:为元素添加动态效果,一般与过渡配合使用 概念:改变盒子在平面内的形态(位移、旋转、缩放、倾斜) 平面转换又叫 2D 转换 平移 属性:transform: translate(X轴移动距离,Y轴移动…...
【Python】 生成二维码
创建了一个使用 python 创建二维码的程序。 下面是生成的程序的图像。 功能描述 输入网址(URL)。 输入二维码的名称。 当单击 QR 码生成按钮时,将使用 QRname 中输入的字符将 QR 码生成为图像。 程序代码 import qrcode import tkinterd…...
Qt与Sqlite3
操作流程: (1)与数据库连接 (2)进行增删改查操作 (3)关闭数据库 示例: 参考: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 (注意:这是笔者所缺失的结…...
【外观模式】SpringBoot集成mail发送邮件
前言 发送邮件功能,借鉴 刚果商城,根据文档及项目代码实现。整理总结便有了此文,文章有不对的点,请联系博主指出,请多多点赞收藏,您的支持是我最大的动力~ 发送邮件功能主要借助 mail、freemarker以及rocke…...
GUAVA 工具类
Guava是一个Google的开源Java库,常用的工具: 集合工具类,包括Lists(创建:newArrayList、newLinkedList等)、Sets(创建:newHashSet、newLinkedHashSet等)和Mapsÿ…...
高云GW1NSR-4C开发板上手使用
1.开发板 核心板,主芯片GW1NSR-LV4CQN48P,丝印文字“奥陶纪Octet,QQ群808770961”: 晶振:27MHz,22引脚 两个按键:靠近中间,23引脚,按下为低电平;靠近外侧&…...
androidstudio设置内存
androidstudio一直 scanning files to index,需要去设置内存: 操作如下:...
[ 蓝桥杯Web真题 ]-Markdown 文档解析
目录 介绍 准备 目标 规定 思路 补充知识 解法参考 介绍 Markdown 因为其简洁的语法大受欢迎,已经成为大家写博客或文档时必备的技能点,众多博客平台都提倡用户使用 Markdown 语法进行文章书写,然后再发布后,实时的将其转化…...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...
uniapp 对接腾讯云IM群组成员管理(增删改查)
UniApp 实战:腾讯云IM群组成员管理(增删改查) 一、前言 在社交类App开发中,群组成员管理是核心功能之一。本文将基于UniApp框架,结合腾讯云IM SDK,详细讲解如何实现群组成员的增删改查全流程。 权限校验…...
<6>-MySQL表的增删查改
目录 一,create(创建表) 二,retrieve(查询表) 1,select列 2,where条件 三,update(更新表) 四,delete(删除表…...
ubuntu搭建nfs服务centos挂载访问
在Ubuntu上设置NFS服务器 在Ubuntu上,你可以使用apt包管理器来安装NFS服务器。打开终端并运行: sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享,例如/shared: sudo mkdir /shared sud…...
MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例
一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...
第25节 Node.js 断言测试
Node.js的assert模块主要用于编写程序的单元测试时使用,通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试,通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...
Python爬虫(二):爬虫完整流程
爬虫完整流程详解(7大核心步骤实战技巧) 一、爬虫完整工作流程 以下是爬虫开发的完整流程,我将结合具体技术点和实战经验展开说明: 1. 目标分析与前期准备 网站技术分析: 使用浏览器开发者工具(F12&…...
Nginx server_name 配置说明
Nginx 是一个高性能的反向代理和负载均衡服务器,其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机(Virtual Host)。 1. 简介 Nginx 使用 server_name 指令来确定…...
leetcodeSQL解题:3564. 季节性销售分析
leetcodeSQL解题:3564. 季节性销售分析 题目: 表:sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...
10-Oracle 23 ai Vector Search 概述和参数
一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI,使用客户端或是内部自己搭建集成大模型的终端,加速与大型语言模型(LLM)的结合,同时使用检索增强生成(Retrieval Augmented Generation &#…...
