数据结构和算法专题---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 语法进行文章书写,然后再发布后,实时的将其转化…...
从WWDC看苹果产品发展的规律
WWDC 是苹果公司一年一度面向全球开发者的盛会,其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具,对过去十年 WWDC 主题演讲内容进行了系统化分析,形成了这份…...
shell脚本--常见案例
1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件: 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...
mongodb源码分析session执行handleRequest命令find过程
mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程,并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令,把数据流转换成Message,状态转变流程是:State::Created 》 St…...
可靠性+灵活性:电力载波技术在楼宇自控中的核心价值
可靠性灵活性:电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中,电力载波技术(PLC)凭借其独特的优势,正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据,无需额外布…...
【JVM】- 内存结构
引言 JVM:Java Virtual Machine 定义:Java虚拟机,Java二进制字节码的运行环境好处: 一次编写,到处运行自动内存管理,垃圾回收的功能数组下标越界检查(会抛异常,不会覆盖到其他代码…...
【机器视觉】单目测距——运动结构恢复
ps:图是随便找的,为了凑个封面 前言 在前面对光流法进行进一步改进,希望将2D光流推广至3D场景流时,发现2D转3D过程中存在尺度歧义问题,需要补全摄像头拍摄图像中缺失的深度信息,否则解空间不收敛…...
k8s业务程序联调工具-KtConnect
概述 原理 工具作用是建立了一个从本地到集群的单向VPN,根据VPN原理,打通两个内网必然需要借助一个公共中继节点,ktconnect工具巧妙的利用k8s原生的portforward能力,简化了建立连接的过程,apiserver间接起到了中继节…...
多种风格导航菜单 HTML 实现(附源码)
下面我将为您展示 6 种不同风格的导航菜单实现,每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...
零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)
本期内容并不是很难,相信大家会学的很愉快,当然对于有后端基础的朋友来说,本期内容更加容易了解,当然没有基础的也别担心,本期内容会详细解释有关内容 本期用到的软件:yakit(因为经过之前好多期…...
Java线上CPU飙高问题排查全指南
一、引言 在Java应用的线上运行环境中,CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时,通常会导致应用响应缓慢,甚至服务不可用,严重影响用户体验和业务运行。因此,掌握一套科学有效的CPU飙高问题排查方法&…...
