算法基本思想(结尾附上记忆口诀)

2024-03-05 09:36

本文主要是介绍算法基本思想(结尾附上记忆口诀),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

算法基本思想(结尾附上记忆口诀)

  • 贪心
  • 分治
  • 枚举
  • 动态
  • 回溯
  • 递归(兄弟思想-递推)

这篇文章说的这些思想网上一大堆,可以不看。直接关注结尾自创口诀,希望给你提供一点帮助。

递归

概述

在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法

特点

  1. 边界条件
  2. 规模递减

能解决的问题

  1. 数据的定义是按递归定义的。如Fibonacci函数。
  2. 问题解法按递归算法实现。如Hanoi问题。
  3. 数据的结构形式是按递归定义的。如二叉树、广义表等

递归解题的基本套路

  1. 明确这个函数的功能
  2. 递推公式 自上而下的分析
  3. 补充到步骤1中定义的函数中
  4. 时间复杂度的计算

参考文献

一文看懂什么递归(算法小结)
https://zhuanlan.zhihu.com/p/94748605
https://juejin.im/post/6844904008595816462

分治

概述

在计算机科学中,分治法是建基于多项分支递归的一种很重要的算法范式。字面上的解释是"分而治之",就是把一个复杂的问题分成两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并

步骤

分解(将原问题分解成一系列子问题)
求解(递归的求解各子问题,若子问题足够小,则直接求解)
合并(将子问题的解合并成原问题的解)

适用情况

如排序算法(归并排序、快速排序)、傅立叶变换(快速傅立叶变换)

贪心

概述

又称贪婪算法,是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是最好或最优的算法。[1]比如在旅行推销员问题中,如果旅行员每次都选择最近的城市,那这就是一种贪心算法。
贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说,问题能够分解成子问题来解决,子问题的最优解能递推到最终问题的最优解。
贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择,不能回退。动态规划则会保存以前的运算结果,并根据以前的结果对当前进行选择,有回退功能。

贪心算法的基本思路

  1. 根据问题来建立数学模型,一般面试题会定义一个简单模型;
  2. 把待求解问题划分成若干个子问题,对每个子问题进行求解,得到子问题的局部最优解;
  3. 把子问题的局部最优解进行合并,得到最后基于局部最优解的一个解,即原问题的答案。

具有以下性质可以使用贪心算法
最优子结构
贪心选择性质

适用情况

贪心法可以解决一些最优化问题,如:求图中的最小生成树、求哈夫曼编码……对于其他问题,贪心法一般不能得到我们所要求的答案。一旦一个问题可以通过贪心法来解决,那么贪心法一般是解决这个问题的最好办法。由于贪心法的高效性以及其所求得的答案比较接近最优结果,贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。在不同情况,选择最优的解,可能会导致辛普森悖论(Simpson’s Paradox),不一定出现最优的解。

贪心算法在Data Science领域都被资泛应用,特别是金融工程。其中一个贪心算法例子就是Ensemble method

实例

最小生成树、求哈夫曼编码、活动选择问题

回溯

概述

回溯法:有"通用的解题法"之称,可以系统地搜索一个问题的所有解或任一解。在包含问题的所有解的解空间树时,按照深度优先的策略,从根节点触发搜索解空间树。搜索至任一结点时,总是先判断该结点是否肯定不包含问题的解,如果不包含,则跳过对以该结点为根的子树的搜索,逐层向其祖先结点回溯;否则,进入该子树,继续按深度优先的策略进行搜索。

可以理解为先进行深度优先搜索,一直向下探测,当此路不通时,返回上一层探索另外的分支,重复此步骤,这就是回溯,意为先一直探测,当不成功时再返回上一层。

适用情况

实例

八皇后问题、迷宫类问题

枚举

概述

枚举算法的思想是:将问题的所有可能的答案一一列举,然后根据条件判断此答案是否合适,保留合适的,丢弃不合适的。

解题思路

确定枚举对象、枚举范围和判定条件。
逐一列举可能的解,验证每个解是否是问题的解。

动态

概述

动态规划在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题,它们的结果都逐渐被计算并被保存,从简单的问题直到整个问题都被解决。因此,动态规划保存递归时的结果,因而不会在解决同样的问题时花费时间。
动态规划只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解(对有些问题这个要求并不能完全满足,故有时需要引入一定的近似)。简单地说,问题能够分解成子问题来解决。

适用情况

  1. 最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的,我们就称该问题具有最优子结构性质(即满足最优化原理)。最优子结构性质为动态规划算法解决问题提供了重要线索。
  2. 无后效性。即子问题的解一旦确定,就不再改变,不受在这之后、包含它的更大的问题的求解决策影响。
  3. 子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时,每次产生的子问题并不总是新问题,有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质,对每一个子问题只计算一次,然后将其计算结果保存在一个表格中,当再次需要计算已经计算过的子问题时,只是在表格中简单地查看一下结果,从而获得较高的效率,降低了时间复杂度。

实例

0-1背包问题、最长公共子序列

记忆口诀

贪心小蔡,

分治湾湾,

人行

湾湾回归

(关注:鲁班曰)

这篇关于算法基本思想(结尾附上记忆口诀)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/776062

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

hdu1496(用hash思想统计数目)

作为一个刚学hash的孩子,感觉这道题目很不错,灵活的运用的数组的下标。 解题步骤:如果用常规方法解,那么时间复杂度为O(n^4),肯定会超时,然后参考了网上的解题方法,将等式分成两个部分,a*x1^2+b*x2^2和c*x3^2+d*x4^2, 各自作为数组的下标,如果两部分相加为0,则满足等式; 代码如下: #include<iostream>#include<algorithm

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

基本知识点

1、c++的输入加上ios::sync_with_stdio(false);  等价于 c的输入,读取速度会加快(但是在字符串的题里面和容易出现问题) 2、lower_bound()和upper_bound() iterator lower_bound( const key_type &key ): 返回一个迭代器,指向键值>= key的第一个元素。 iterator upper_bou

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费

【IPV6从入门到起飞】5-1 IPV6+Home Assistant(搭建基本环境)

【IPV6从入门到起飞】5-1 IPV6+Home Assistant #搭建基本环境 1 背景2 docker下载 hass3 创建容器4 浏览器访问 hass5 手机APP远程访问hass6 更多玩法 1 背景 既然电脑可以IPV6入站,手机流量可以访问IPV6网络的服务,为什么不在电脑搭建Home Assistant(hass),来控制你的设备呢?@智能家居 @万物互联