算法基础

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

相关文章

  • java注解示例程序

    MyAnno.java package com.yawn.annotation; import java.lang.annotation.Documented...

    yawn
  • spring mvc 时间日期转换(@DateTimeFormat 注解)

    两种用法示例: @GetMapping("/date") public String datest(@DateTimeFormat(iso=ISO.D...

    yawn
  • Timer类的schedule()方法

    timer.schedule(new MyTask(),long time1,long timer2); 第一个参数,是 TimerTask 类,在包:impo...

    yawn
  • 五分钟学算法:二叉树的后序遍历

    下面这种写法使用了一个辅助结点p,这种写法其实可以看作是一个模版,对应的还有前序和后序的模版写法,形式很统一,方便于记忆。上上篇更新前序的和上篇更新的中序文章中...

    五分钟学算法
  • 数据结构 二叉排序树

    二叉排序树中查找某关键字时,查找过程类似于次优二叉树,在二叉排序树不为空树的前提下,首先将被查找值同树的根结点进行比较,会有 3 种不同的结果:

    Debug客栈
  • 9.3 动态查找表

    (1)和次优二叉树相对,二叉排序树是一种动态树表。其特点是,树点的结构通常不是一次生成的,而是在查找过程中,当树中不存在关键字等于给定值的结点时再进行插入。

    闫小林
  • Vue2 dist 目录下各个文件的区别

    简单来说, 完整构建 和 运行时构建的区别就是, 可不可以用template选项, 和文件大一点,小一点。而按照不同的规范可以运行在不同的开发环境中。

    挥刀北上
  • Atomwise:与Lilly就AI驱动的药物研发项目达成多年协议

    Atomwise宣布与美国公司Eli Lilly达成一项多年协议,将应用Atomwise的人工智能专利技术,支持Lilly公司的临床前药物研发工作。两家公司将在...

    AiTechYun
  • linux系统编程之基础必备(七):read/write函数与(非)阻塞I/O的概念

    一、read/write 函数 read函数从打开的设备或文件中读取数据。 #include <unistd.h> ssize_t read(int fd,...

    s1mba
  • 一张图看懂世界石油分布?用Python轻松搞定!

    【导语】:今天我们教你用Python画出世界石油分布桑基图,Python技术部分可以直接看第四部分。

    CDA数据分析师

扫码关注云+社区

领取腾讯云代金券