算法基础

分治法的基本思想: 将一个规模为 n 的问题分解为 k 各规模较小的子问题, 这些子问题互相独立且与原问题是同类型问题。 递归地解这些子问题, 然后把各个子问题的解合并得到原问题的解。

分治法所能解决的问题一般具有的几个特征是: 该问题规模缩小到一定程度就可以容易地解决; 该问题可以分解为若干个规模较小的同类型问题; 利用该问题分解出的子问题的解可以合并为该问题的解; 原问题分解出的各个子问题是相互独立的, 即子问题之间不包含公共的子问题。

分治法可以解决的具体问题:矩阵连乘、大数乘法、二分法搜索、快速排序、合并排序

合并排序的基本思想: 将待排序元素分成大小大致相同的 2 个子集合, 分别对 2 个子集合进行排序,然后将已排序的两个子集合合并成排好序的集合。 如果分割后的子集合还是比较大, 则继续分治, 直到分成的子集合只包含一个元素。 合并排序的时间复杂度是 O(nlogn) , 是排序算法中的渐近最优算法。

快速排序的基本思想: 对于输入的数组, 以第 1 个元素为基准元素将数组划分成 3 段, 基准元素在中间, 小于等于基准元素的在前面, 大于等于基准元素的在后面; 对第 1 段和第 3 段驻足重复以上过程, 直到每一部分只有一个元素为止。 快速排序的平均时间复杂度是O(nlogn)。

分治法与动态规划法的异同: 相同点是, 将待求解的问题分解成若干个子问题, 先求解子问题, 然后从这些子问题的解得到原问题的解; 不同点是, 适合用动态规划法求解的问题, 经分解得到的子问题可以不相互独立, 而用分治法求解的问题, 经分解得到的子问题往往是相互独立的。设计动态规划算法的主要步骤: 证明最优子结构性质, 确定递归式, 计算最优值, 构造最优解。

动态规划算法的两个基本要素是( 最优子结构性质) 和( 重叠子问题性质)。

贪心算法的基本思想: 首先根据题意, 选取一种度量标准( 即贪心策略), 然后通过一系列的选择得到问题的解。 它所做出的每一个选择都是当前状态下局部最好选择。

单源最短路径Dijkstra算法、最小生成树算法prim和Kruskal算法都是贪心算法。

用回溯法解题的一个显著特征是搜索过程中动态产生问题的解空间。 在任何时刻, 算法只保存从根结点到当前扩展结点的路径。 如果解空间树中从根结点到叶结点的最长路径的长度为 h(n) , 则回溯法所需的计算空间通常为 O(h(n))。

回溯法的基本步骤:( 1) 针对所给问题, 定义问题的解空间;( 2) 确定易于搜索的解空间结构;( 3)以深度优先方式搜索解空间, 并在搜索过程中用剪枝函数避免无效搜索。

分支限界法的基本思想: 分支限界法常以广度优先或最小耗费( 最大效益) 优先的方式搜索问题的解空间树。 在分支限界法中, 每个活结点只有一个机会成为扩展结点。 活结点一旦成为扩展结点, 就一次性产生其所有子结点。 在这些子结点中, 导致不可行解或导致非最优解的子结点被舍弃, 其余子结点被加入活动结点表中。 此后, 从活结点表中取下一个结点成为当前扩展结点, 并重复上述过程, 直到找到所需解或活动结点列表为空为止。

分支限界法的搜索策略是: 在扩展结点处, 先生成它的所有子结点, 根据剪枝函数将满足条件的子结点加入活结点表中, 然后再从当前的活结点表中选择一个最有利的结点作为下一个扩展结点。

分支限界法与回溯法的异同: 相同点是, 都是一种在问题的解空间树种搜索解得算法; 不同点是, 求解目标不同( 回溯可以找全部解可以找最优解, 分支限界找最优解), 搜索方式不同( 回溯深度优先, 分支限界广度优先或按优先级), 对扩展结点的扩展方式不同( 回溯一次一个子结点, 分支限界一次产生所有结点), 对存储空间的要求不同( 回溯用一个数组存放活结点, 分支限界用一个优先队列存放活结点)。

用确定性图灵机在多项式时间内可解的判定问题称为 P 类问题; 用非确定性图灵机在多项式时间内可解的问题称为 NP 类问题; 对于一个 NP 问题 X, 如果其他所有的 NP 问题都可以在多项式时间内归约为 X, 则 X 称为 NP 完全问题。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏hanlp学习笔记

hanlp中的N最短路径分词

N-最短路径 是中科院分词工具NLPIR进行分词用到的一个重要算法,张华平、刘群老师在论文《基于N-最短路径方法的中文词语粗分模型》中做了比较详细的介绍。该算法...

730
来自专栏Albert陈凯

技术面试要了解的算法和数据结构知识

目录 在线练习 在线编程面试 数据结构 算法 贪心算法 位运算 复杂度分析 视频教程 面试宝典 计算机科学资讯 文件结构 在线练习 Le...

2765
来自专栏calmound

KMP专题

POJ 2406 Power Strings http://poj.org/problem?id=2406 题意:找出s字符窜由多少个重复子窜循环构成 分析:K...

2958
来自专栏web前端教室

javascript 红皮高程(14)

image.png 接下为JS的位操作符,这个东西一般不常用,但用熟了之后在特定场景中效率惊人。 但这个位运算的相关知识啊,我数学不好,是学一次忘一次,忘一...

1846
来自专栏C/C++基础

最大子数组问题

炒股的人都知道,股票的价格是不稳定的。若想从炒股中赚钱,必须“低买高卖”,就是低价买进,高价卖出,赚取中间差价。那么给定一段时间,每一天都对应着不同的股价,如何...

922
来自专栏码匠的流水账

敏感词检测算法小结

经典的AC算法由三部分构成,goto表,fail表和output表,共包含四种具体的算法,分别是计算三张查找表的算法以及AC算法本身。

1272
来自专栏专注数据中心高性能网络技术研发

[LeetCode]Array主题系列{35,39,40,48题}

1. 内容介绍 开一篇文章记录在leetcode中array主题下面的题目和自己的思考以及优化过程,具体内容层次按照{题目,分析,初解,初解结果,优化解,优化解...

3098
来自专栏算法channel

常用排序算法代码兑现

主要推送关于对算法的思考以及应用的消息。坚信学会如何思考一个算法比单纯地掌握100个知识点重要100倍。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎...

34011
来自专栏小樱的经验随笔

HUST 1588 辗转数对

1588 - 辗转数对 时间限制:1秒 内存限制:128兆 155 次提交 27 次通过 题目描述假设当前有一个数对(a, b),我们可以通过一步将这个数对...

3309
来自专栏数据结构笔记

数据结构(二):算法及其描述

数据元素之间的关系有逻辑关系和物理关系,对应的操作有逻辑结构上的操作功能和具体存储结构上的操作实现。

1205

扫码关注云+社区