算法基础

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

相关文章

来自专栏专知

2018年SCI期刊最新影响因子排行,最高244,人工智能TPAMI9.455

2018年6月26日,最新的SCI影响因子正式发布,涵盖1万2千篇期刊。CA-Cancer J Clin 依然拔得头筹,其影响因子今年再创新高,达244.585...

1272
来自专栏一个会写诗的程序员的博客

java.base.jmod

/Library/Java/JavaVirtualMachines/jdk-9.jdk/Contents/Home/jmods$ jmod list java....

1112
来自专栏Hadoop数据仓库

Oracle sqlldr 如何导入一个日期列

1. LOAD DATA INFILE * INTO TABLE test FIELDS TERMINATED BY X'9' TRAILING NULLCO...

1786
来自专栏吴伟祥

Apache POI总结 原

Apache POI  是用Java编写的免费开源的跨平台的 Java API,Apache POI提供API给Java程式对Microsoft Office格...

721
来自专栏余生开发

echarts太阳分布图-饼图来回穿梭

var dom = document.getElementById("container");

1142
来自专栏JMCui

MongoDB系列五(地理空间索引与查询).

Volvo Today, Volvo announced i...

2712
来自专栏我和未来有约会

简练的视图模型 ViewModel

patterns & practices Developer Center 发布了 Unity Application Block 1.2 for Silver...

2159
来自专栏linux驱动个人学习

高通msm8909耳机调试

1、DTS相应修改: DTS相关代码:kernel/arch/arm/boot/dts/qcom/msm8909-qrd-skuc.dtsi: 1 s...

7345
来自专栏Pulsar-V

Save Camera Document

#pragma once #include "HCCamera.h" #include <time.h> #include <cstdio> #incl...

2818
来自专栏Ryan Miao

ehcache报错

jfinal2.0+tomcat7+ehcache2.6.11+Linux Linux version 2.6.18-164.el5 (mockbuild@x8...

3719

扫码关注云+社区