程序员:Java数据结构与算法——第十六章·算法设计技术详解

                                                            Java数据结构与算法-第十六章·算法设计

16.1引言

在求解一个新问题时,通常的思路是寻找当前问题与已解决问题之间的相似之处,从而轻松找到新问题的求解方法。

本章将对各种算法按照不同的方法进行分类,然后在随后的3章中分别介绍3个算法设计思想(即贪婪、分治和动态规划)。

16.2分类

关于算法的分类有很多种方法,下面列出了其中的一些分类方法:

●实现方法

●设计方法

●其他分类方法

16.3 按实现方法分类

1.递归或迭代

       递归算法指算法反复地调用自身,直到满足某个基准条件。它在C、C++等函数式编程语言中被普遍采用。迭代算法中经常使用循环等结构,并有时采用栈和队列等数据结构来求解问题。

       有些问题适合用递归实现,另一些问题则适合用迭代实现。例如,汉诺塔问题的递归实现非常容易理解。每一个递归实现均可以改成迭代实现,反之亦然。

2.过程式或声明式(非过程)

       对于声明式编程语言,只需要指明所需达到的目标,而无需给出实施的细节。过程式编程语言需要指明得到期望结果的具体步骤。例如,SQL更倾向于是一种声明式语言,而非过程式,因为查询操作不需要给出查询的具体步骤。而C、PHP、PERL等则是过程式语言的例子。

3.串行或并行或分布式

       当讨论算法时,一般认为计算机- -次执行- -条指令,这就是所谓的串行程序(算法)。并行算法则利用计算机体系结构的特点一次处理多条指令,并将原问题分割成多个子问题,然后将它们分配到多个处理器或者线程来分别求解。迭代算法一般是可并行化的。如果将并行算法分布到不同的机器上,则将这样的算法称为分布式算法。

4.确定性或不确定性

       确定性算法基于预定义的过程来求解问题,而不确定性算法在每一步通过某种启发式规则来推测最优解。

5.精确或近似

       许多问题不一定能够找出最优解。因此,那些能够给出最优解的算法称为精确算法。在计算机科学中,对于那些不能够提供精确解的问题,常常给出近似算法。近似算法往往用于求解NP难问题(详细描述见第20章)。

16. 4按设计方法分类

       除了实现方法外,还可以根据设计方法来对算法进行分类。

1.贪婪法

       贪婪算法将问题分为多个阶段。在每一个阶段,选取当前状态的最优决策,而不考虑对后续决策的影响。这意味着算法在执行过程中会选取某些局部最优解。贪婪法假设通过局部最优解可以获得全局最优解。

2.分治法

分治法按以下3个步骤求解问题:

       1)分:将原问题分成多个子问题,这些子问题是与原问题类型相同的规模更小的实例。

       2)递归:递归求解子问题。

       3)治:合理地组合子问题的解。

例子:归并排序和二分查找算法。

3.动态规划方法

       动态规划( Dynamic Programming,DP)与 备忘录方法相结合。动态规划与分治法的不同是:分治法的子问题之间不存在依赖关系,而DP的子问题存在重叠。通过备忘录技术(用一个表保存已解决子问题的答案),动态规划法可将许多问题的复杂度从指数级降低为多项式级(O(n2)、O(n')等)。动态规划与递归的不同之处在于递归调用的备忘录技术。当各个子问题之间相互独立时,没有重复调用,则这种备忘录技术对降低复杂度没有任何帮助,因此动态规划不是一种适用于所有问题的方法。通过备忘录技术(用一个表保存已解决子问题的答案),动态规划可以将算法复杂度从指数级降低为多项式级。

4.线性规划方法

       在线性规划中,在满足不等式约束的条件下,最大化(或最小化)输入变量的线性函数。许多问题(如,有向图的最大流)可以采用线性规划方法。

5.归约(转化和求解)

       这种方法的思想是,将一复杂的问题转化和求解为--个已有渐近最优解的已知问题。该方法的目标是寻找一个归约算法,使得归约后的算法复杂度不会更高。例如,寻找线性表中中位数的算法是:首先将线性表排序,然后寻找有序表的中间值。这两个步骤分别称为转化和求解。

16.5 其他分类法

1.按研究领域分类

       在计算机科学中,每-个领域都有各自的问题并需要有效的算法。例如,查找算法、排序算法、归并算法、数值算法、图算法、字符串算法、几何算法、组合算法、机器学习、加密、并行算法、数据解压缩算法等。

2.按复杂度分类

       算法根据与输入规模相关的求解时间进行分类。有些算法具有线性时间复杂度(O(n)),另一些算法耗费指数级时间,甚至某些算法从不停止。注意某些问题可能有不同复杂度的多种求解算法。

3.随机算法

       有些算法需要进行随机选择。对于某些问题,其最快的求解算法必须涉及随机操作,例子:快速排序。

4.分支定界、枚举和回溯

这些方法在人工智能领域都有使用,这里不展开叙述。对于回溯方法,可参考第2章。

注意:在后面的三章中,将分别讨论贪婪、分治和动态规划三种算法设计技术。关注这三种技术,因为用这三种技术求解的问题比其他技术多。

热门文章

暂无图片
编程学习 ·

MIT 计算机操作环境导论Missing Semester Lesson 10 Q&A

最后一节课,我们回答学生提出的问题:学习操作系统相关内容的推荐,比如进程,虚拟内存,中断,内存管理等你会优先学习的工具有那些?使用 Python VS Bash脚本 VS 其他语言?source script.sh 和 ./script.sh 有什么区别?各种软件包和工具存储在哪里?引用过程是怎样的? /bi…
暂无图片
编程学习 ·

Mathmatica多项式带余除法代码

几乎没有调用内置函数,除了求多项式最高次数时用了一下 Exponent[] (*解析多项式*) (*将f=a0+a1*x+...+an*x^n解析成{{a0,0},{a1,1},...,{an,n}}的形式*) polyCoefficients[f_] := Module[{rules1 = {c_*base_^power_ -> {c, power},base_^power_ -> {1, power},c_*x_ -…
暂无图片
编程学习 ·

mysql的语句执行原理详解

需求:select user,host from mysql.user; 以上面的一条命令为例,如何将数据返回的,下面进行详细的阐述:SQL层总结: 语法、语义(数据XX语言)、权限(grant)检查完毕后—> 根据解析器生成解析树—>优化器代价评估—>然后得出执行计划—>执行器执行—>在那…
暂无图片
编程学习 ·

php发送stmp邮件类 给有需要的人

<?php/*** email smtp (support php7)** Modified by: Reson 2019/06** More: http://www.wan0551.com**/class Smtp {/* Public Variables */public $smtp_port;public $time_out;public $host_name;public $log_file;public $relay_host;public $debug;public $auth;pu…
暂无图片
编程学习 ·

ECharts雷达图详细配置说明

// 指定图表的配置项和数据 var option = {backgroundColor: rgba(204,204,204,0.7 ),// 背景色,默认无背景 rgba(51,255,255,0.7)title: {text: 各教育阶段男女人数统计,link: https://www.xxx.com,target: blank,top: 5%,left: 3%,textStyle: {color: #fff,fontSize: 20,…
暂无图片
编程学习 ·

培训网站比较-CSDN-51CTO-慕课网

本人是从事互联网行业,从码农到部门负责人,一路走来,最让我感受深刻的是,技术每天在更新迭代,自己一定要跟上脚步,不然很容易被淘汰。不管是作为技术人员还是部门管理者,技术能力必须得到重视。作为部门负责人,必须督促大家学习技术。我讲讲这几年在这方面的经历:一开…
暂无图片
编程学习 ·

浅析深究什么是SOA

1. 背景 IT行业就是术语和缩写流行的行业,各大厂商都喜欢隔三差五地推出一些新概念。为了不落人后,大家都喜欢争先恐后地跟进。有深入研究、务实研发的供应商,能够将概念落地,不断推出创新的产品和服务,赢得竞争优势。但“贴标签”的也大有人在,而且趋势是越贴越多,跟风…
暂无图片
编程学习 ·

ps处理几亿个像素点的照片时,如何保存为几十兆而又很清晰

最近几天在做年级的毕业照,照片像素大小为24400*14640,在硬盘里有1.16G。 这个时候如果用ps直接存储为png格式的话,保存的照片非常模糊,基本看不清脸。当时很苦恼,还以为几亿个像素的照片没办法既小又高清。对于这么大的照片,我百度了一下一般保存为tif格式。这是相机拍照…
暂无图片
编程学习 ·

网络管理

什么是网络管理 网络管理的基础设施 因特网标准管理框架 管理信息结构:SMI 管理信息库:MIB SNMP协议运行和传输映射 安全性和管理 ASN.1
暂无图片
编程学习 ·

13年蓝桥杯javaB组

13年蓝桥杯javaB组1.末世纪的星期天2.马虎的算式3.振兴中华4.黄金分数割5.有理数类6.三部排序7.错误票据 1.末世纪的星期天 曾有邪教称1999年12月31日是世界末日。当然该谣言已经不攻自破。 还有人称今后的某个世纪末的12月31日,如果是星期一则会是世界末日 有趣的是,任何一个…
暂无图片
编程学习 ·

SwiftUI 2020年WWDC演示示例

整体效果代码实现 文件目录SandwichesApp.swift import SwiftUI@main struct SandwichesApp: App {// 定义一个私有的状态对象 store@StateObject private var store = SandwichStore()var body: some Scene {WindowGroup {// 将store传递给列表页ContentView(store: store)}} …
暂无图片
编程学习 ·

你(真的)编写异常安全代码吗? [关闭]

本文翻译自:Do you (really) write exception safe code? [closed] Exception handling (EH) seems to be the current standard, and by searching the web, I can not find any novel ideas or methods that try to improve or replace it (well, some variations exist, b…
暂无图片
编程学习 ·

java.lang.UnsupportedOperationException异常处理

今天写代码的时候遇到的,原因是因为使用Arrays.asList()将数组转为list之后,想调用add方法增加元素时的异常,后来查了资料才发现猫腻 在Arrays中有一个方法Arrays.asList(),这个平常我们都用作数组转List的,但是这个方法转出来的List是无法进行add/remove操作的,原因是由…
暂无图片
编程学习 ·

数据库原理及应用教程陈志泊-第三章课后习题

一、选择题1. B 2. A 3. C 4. B 5. C 6. C7. B 8. D 9. A 10. D 11. C 12. D二、填空题1. 结构化查询语言2. 数据查询、数据定义、数据操纵、数据控制3. 外模式、模式、内模式4. 数据库、事务日志5. NULL/NOT NULL 、 UNIQUE 约束、 PRIMARY KEY 约束、 FOREIGN KEY …
暂无图片
编程学习 ·

mysql怎么连接navicat

可能出现下面的问题远程连接发现没有什么问题 在命令行 mysql可以正常使用执行三条指令就可以解决