算法基础

分治法的基本思想: 将一个规模为 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 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

P1003 铺地毯

题目描述 为了准备一个独特的颁奖典礼,组织者在会场的一片矩形区域(可看做是平面直角坐标系的第一象限)铺上一些矩形地毯。一共有 n 张地毯,编号从 1 到n 。现...

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

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

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

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

[LeetCode]Array主题系列{1,11,15,16,18,26,27,31,33,34题}

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

2826
来自专栏数据结构与算法

BZOJ3687: 简单题(dp+bitset)

Description 小呆开始研究集合论了,他提出了关于一个数集四个问题: 1.子集的异或和的算术和。 2.子集的异或和的异或和。 3.子集的算术和的算术和...

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

BZOJ 1411&&Vijos 1544 : [ZJOI2009]硬币游戏【递推,快速幂】

1411: [ZJOI2009]硬币游戏 Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 897  Solve...

2545
来自专栏大数据和云计算技术

算法基础8:平衡树之红黑树

算法是基础,小蓝同学准备些总结一系列算法分享给大家,这是第8篇《平衡查找树概述》,非常赞!希望对大家有帮助,大家会喜欢! 前面系列文章: 归并排序 #算法...

2925
来自专栏计算机视觉与深度学习基础

Leetcode 39 Combination Sum

Given a set of candidate numbers (C) and a target number (T), find all unique c...

1988
来自专栏算法与数据结构

PTA 社交网络图中结点的“重要性”计算(30 分)

7-12 社交网络图中结点的“重要性”计算(30 分) 在社交网络中,个人或单位(结点)之间通过某些关系(边)联系起来。他们受到这些关系的影响,这种影响可以理解...

19910
来自专栏文武兼修ing——机器学习与IC设计

logN复杂度估算与一些示例logN复杂度估算logN复杂度算法举例

logN复杂度估算 logN复杂度的算法可以认为具有以下特性: 用常数时间将问题的大小削减为某一部分(通常是1/2) 例如分治法求最大子串问题,将一个$O(N...

2506
来自专栏ACM算法日常

算法合集 | 无限的路(递推) - HDU 2073

递推和递归有着很多的相似之处,甚至可以看做是递归的反向。递归的目的性很强,只解需要解的问题,递推有点“步步为营”的味道,不断的利用已有的信息推导...

421

扫描关注云+社区