算法4基础

A. 算法分析中动态规划的四个基本步骤

1、描述优解的结构特征。

2、递归地定义一个最优解的值。

3、自底向上计算一个最优解的值。

4、从已计算的信息中构造一个最优解。

B. 算法的概念

算法（Algorithm）是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。在计算机科学中，算法要用计算机算法语言描述，算法代表用计算机解一类问题的精确、有效的方法。算法+数据结构=程序，求解一个给定的可计算或可解的问题，不同的人可以编写出不同的程序，来解决同一个问题，这里存在两个问题：一是与计算方法密切相关的算法问题；二是程序设计的技术问题。算法和程序之间存在密切的关系。
算法是一组有穷的规则，它们规定了解决某一特定类型问题的一系列运算，是对解题方案的准确与完整的描述。制定一个算法，一般要经过设计、确认、分析、编码、测试、调试、计时等阶段。
对算法的学习包括五个方面的内容：① 设计算法。算法设计工作是不可能完全自动化的，应学习了解已经被实践证明是有用的一些基本的算法设计方法，这些基本的设计方法不仅适用于计算机科学，而且适用于电气工程、运筹学等领域；② 表示算法。描述算法的方法有多种形式，例如自然语言和算法语言，各自有适用的环境和特点；③确认算法。算法确认的目的是使人们确信这一算法能够正确无误地工作，即该算法具有可计算性。正确的算法用计算机算法语言描述，构成计算机程序，计算机程序在计算机上运行，得到算法运算的结果；④ 分析算法。算法分析是对一个算法需要多少计算时间和存储空间作定量的分析。分析算法可以预测这一算法适合在什么样的环境中有效地运行，对解决同一问题的不同算法的有效性作出比较；⑤ 验证算法。用计算机语言描述的算法是否可计算、有效合理，须对程序进行测试，测试程序的工作由调试和作时空分布图组成。

C. 算法设计基础

python">#python3.7语言第一题用循环算
a=[[3,4,2],
[5,7,3],
[8,2,1],
[3,3,2.9]]

b=[[6,2,4],
[8,5,4],
[10,5,4]]

r=[[0]*3,[0]*3,[0]*3,[0]*3]
foriinrange(len(a)):
forjinrange(len(b[0])):
forkinrange(len(b)):
r[i][j]+=a[i][k]*b[k][j]
forlinr:print(l)

[70,36,36]
[116,60,60]
[74,31,44]
[71.0,35.5,35.6]

#第二题用numpy工具解
importnumpyasnp
ma=np.matrix([
[1,0,3,-1],
[2,1,0,2]])
mb=np.matrix([
[4,1,0],
[-1,1,3],
[2,0,1],
[1,3,4]])
print(ma*mb)

[[9-2-1]
[9911]]

D. 评价算法的四个标准是什么

评价算法的四个标准：

1.正确性

能正确地实现预定的功能，满足具体问题的需要。处理数据使用的算法是否得当，能不能得到预想的结果。

2.易读性

易于阅读、理解和交流，便于调试、修改和扩充。写出的算法，能不能让别人看明白，能不能让别人明白算法的逻辑？如果通俗易懂，在系统调试和修改或者功能扩充的时候，使系统维护更为便捷。

3.健壮性

输入非法数据，算法也能适当地做出反应后进行处理，不会产生预料不到的运行结果。数据的形式多种多样，算法可能面临着接受各种各样的数据，当算法接收到不适合算法处理的数据，算法本身该如何处理呢？如果算法能够处理异常数据，处理能力越强，健壮性越好。

4.时空性

算法的时空性是该算法的时间性能和空间性能。主要是说算法在执行过程中的时间长短和空间占用多少问题。

算法处理数据过程中，不同的算法耗费的时间和内存空间是不同的。

(4)算法4基础扩展阅读：

算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。此外，一个算法还具有下列5个重要的特性。

（1）、有穷性

一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成。

（2）、确定性

算法中每一条指令必须有明确的含义，读者理解时不会产生二义性。即对于相同的输入只能得到相同的输出。

（3）、可行性

一个算法是可行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。

（4）、输入

一个算法有零个或多个的输入，这些输入取自于某个特定的对象的集合。

（5）、输出

一个算法有一个或多个的输出，这些输出是同输入有着某种特定关系的量。

E. 数据结构有哪些基本算法

数据结构是一门研究非数值计算的程序设计问题中的操作对象，以及它们之间的关系和操作等相关问题的学科。

可以理解为：程序设计 = 数据结构 + 算法

数据结构算法具有五个基本特征：输入、输出、有穷性、确定性和可行性。

1、输入：一个算法具有零个或者多个输出。以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件。后面一句话翻译过来就是，如果一个算法本身给出了初始条件，那么可以没有输出。比如，打印一句话：NSLog(@"你最牛逼！");

2、输出：算法至少有一个输出。也就是说，算法一定要有输出。输出的形式可以是打印，也可以使返回一个值或者多个值等。也可以是显示某些提示。

3、有穷性：算法的执行步骤是有限的，算法的执行时间也是有限的。

4、确定性：算法的每个步骤都有确定的含义，不会出现二义性。

5、可行性：算法是可用的，也就是能够解决当前问题。

数据结果的基本算法有：

1、图搜索（广度优先、深度优先）深度优先特别重要

2、排序

3、动态规划

4、匹配算法和网络流算法

5、正则表达式和字符串匹配

6、三路划分-快速排序

7、合并排序（更具扩展性，复杂度类似快速排序）

8、DF/BF 搜索 （要知道使用场景）

9、Prim / Kruskal （最小生成树）

10、Dijkstra （最短路径算法）

11、选择算法

F. 学数据算法结构的基础是什么

算法与数据结构
丛书名： 普能高等院校“十一五”规划教材
作者： 张永，李睿，年福忠编着
出 版 社： 国防工业出版社
出版时间： 2008-8-1
字数： 438000
版次： 1
页数： 296
开本： 16开
印次： 1
纸张： 胶版纸
I S B N ： 9787118058529
包装： 平装
所属分类： 图书 >> 计算机/网络 >> 数据库 >> 数据库理论
定价：￥30.00
内容简介
本书分为基本概念、简单数据结构（线性表、栈、队列）、复杂数据结构（树、图）和算法与数据结构应用（排序、查找、算法设计基础）四部分，详细介绍了常用数据结构和算法的基本概念及其不同的实现方法，对各种数据结构，讨论了在不同存储结构上实现线性和非线性结构的不同运算，并对算法设计的方法和技巧进行了介绍。
本书概念清晰，逻辑严密，重点突出，将抽象的描述与具体的实现结合，便于教学，也使初学者容易掌握其重点内容，有利于自学。本书的算法描述和实现采用类c和C语言。
本书可以作为计算机科学与技术、信息与计算科学和相关专业的本科或大专教材。
图书目录
第一部分基本概念
第1章数据结构基础
1.1问题求解分析
1.2数据结构
1.3数据结构的分类
1.4数据的四种基本存储方法
1.5数据结构三方面的关系
习题
第2章算法及算法分析基础
2.1算法的基本概念
2.2算法的描述
2.3算法分析方法
2.4程序语言的基本语句与基本结构
2.5数组与结构
2.6抽象数据类型的表示与定义
习题
第二部分简单数据结构
第3章线性表
3.1线性表的定义
3.2线性表的运算
3.3线性表的顺序存储结构及实现
3.3.1 线性表的顺序存储结构
3.3.2顺序表的实现
3.4线性表的链式存储结构及实现
3.4.1单链表
3.4.2循环链袁
3.4.3双向链表
3.4.4静态链表
3.4.5顺序表和链表的比较
3.5线性表的应用
习题
第4章栈和队列
4.1 栈
4.1.1 问题的提出
4.1.2定义及其操作
4.1.3栈的存储结构及实现
4.1.4栈的应用举例：表达式求值
4.2 队列
4.2.1 问题的提出
4.2.2队列的定义及操作
4.2.3队列的存储结构及实现
4.2.4队列的应用举例
习题
第5章矩阵和广义表
5.1矩阵的存储
5.2特殊矩阵
5.3稀疏矩阵
5.4广义表
习题
第三部分复杂数据结构
第6章二叉树和树
6.1 二叉树的定义和性质
6.1.1二叉树的定义及相关术语
6.1.2特殊二叉树
6.1.3二叉树的性质
6.2二叉树的存储结构
6.2.1 二叉树的顺序存储表示
6.2.2二叉树的链式存储表示
6.3二叉树的遍历
6.3.1 问题的提出
6.3.2二叉树的遍历算法
6.3.3二叉树遍历的非递归实现
6.3.4遍历算法的应用
6.4二叉树的线索化
6.4.1 线索二叉树的定义
6.4.2线索二叉树的结构
6.4.3二叉树的线索化算法
6.4.4线索二叉树基本操作的实现
6.5二叉树的应用——哈夫曼树
……
第7章图
第8章散列结构
第9章集合结构
第四部分算法与数据结构应用

G. 算法包含哪些要素

算法包含的要素：

一、数据对象的运算和操作：计算机可以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的集合，成为该计算机系统的指令系统。一个计算机的基本运算和操作有如下四类：

1.算术运算：加减乘除等运算

2.逻辑运算：或、且、非等运算

3.关系运算：大于、小于、等于、不等于等运算

4.数据传输：输入、输出、赋值等运算

二、算法的控制结构：一个算法的功能结构不仅取决于所选用的操作，而且还与各操作之间的执行顺序有关。

(7)算法4基础扩展阅读：

算法的五个特性分别是：有穷性、确切性、输入项、输出项、可行性。

1、有穷性

算法的有穷性是指算法必须能在执行有限个步骤之后终止；

2、确切性

算法的每一步骤必须有确切的定义；

3、输入项

一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；

4、输出项

一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；

5、可行性

算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步骤，即每个计算步骤都可以在有限时间内完成（也称之为有效性）。

H. 为什么说算法是计算机科学中最基本的概念

算法是解决一系列问题的清晰指令，是计算机程序运行的基础；计算机科学的基础是计算机的程序能否最终运行，而程序的运行是通过数据结构＋算法实现的（出自《数据结构十算法= 程序》）所以说算法是程序的基础，程序是计算机科学的基础，因此算法是计算机科学的基础。

I. "算法"的基本特征有哪些

一个算法应该具有以下五个重要的特征：

1，有穷性（Finiteness）：算法的有穷性是指算法必须能在执行有限个步骤之后终止；

2，确切性(Definiteness)：算法的每一步骤必须有确切的定义；

3，输入项(Input)：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；

4，输出项(Output)：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；

5，可行性(Effectiveness)：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成（也称之为有效性）。

(9)算法4基础扩展阅读：

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。

也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。

不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

算法中的指令描述的是一个计算，当其运行时能从一个初始状态和（可能为空的）初始输入开始，经过一系列有限而清晰定义的状态，最终产生输出并停止于一个终态。

一个状态到另一个状态的转移不一定是确定的。随机化算法在内的一些算法，包含了一些随机输入。

形式化算法的概念部分源自尝试解决希尔伯特提出的判定问题，并在其后尝试定义有效计算性或者有效方法中成形。

这些尝试包括库尔特·哥德尔、Jacques Herbrand和斯蒂芬·科尔·克莱尼分别于1930年、1934年和1935年提出的递归函数，阿隆佐·邱奇于1936年提出的λ演算，1936年Emil Leon Post的Formulation 1和艾伦·图灵1937年提出的图灵机。

即使在当前，依然常有直觉想法难以定义为形式化算法的情况。

参考资料：网络----算法

J. 作为程序员提高编程能力的几个基础算法

一：快速排序算法

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序n个项目要Ο(nlogn)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(nlogn)算法更快，因为它的内部循环（innerloop）可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法（Divideandconquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

算法步骤：

1从数列中挑出一个元素，称为“基准”（pivot），

2重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。

3递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

二：堆排序算法

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

堆排序的平均时间复杂度为Ο(nlogn) 。

创建一个堆H[0..n-1]

把堆首（最大值）和堆尾互换

3.把堆的尺寸缩小1，并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置

4.重复步骤2，直到堆的尺寸为1

三：归并排序

归并排序（Mergesort，台湾译作：合并排序）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（DivideandConquer）的一个非常典型的应用。

1.申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

2.设定两个指针，最初位置分别为两个已经排序序列的起始位置

3.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

4.重复步骤3直到某一指针达到序列尾

5.将另一序列剩下的所有元素直接复制到合并序列尾

四：二分查找算法

二分查找算法是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。折半搜索每次把搜索区域减少一半，时间复杂度为Ο(logn) 。

五：BFPRT(线性查找算法)

BFPRT算法解决的问题十分经典，即从某n个元素的序列中选出第k大（第k小）的元素，通过巧妙的分析，BFPRT可以保证在最坏情况下仍为线性时间复杂度。该算法的思想与快速排序思想相似，当然，为使得算法在最坏情况下，依然能达到o(n)的时间复杂度，五位算法作者做了精妙的处理。

1.将n个元素每5个一组，分成n/5(上界)组。

2.取出每一组的中位数，任意排序方法，比如插入排序。

3.递归的调用selection算法查找上一步中所有中位数的中位数，设为x，偶数个中位数的情况下设定为选取中间小的一个。

4.用x来分割数组，设小于等于x的个数为k，大于x的个数即为n-k。

5.若i==k，返回x；若i<k，在小于x的元素中递归查找第i小的元素；若i>k，在大于x的元素中递归查找第i-k小的元素。

终止条件：n=1时，返回的即是i小元素。

六：DFS（深度优先搜索）

深度优先搜索算法（Depth-First-Search），是搜索算法的一种。它沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。DFS属于盲目搜索。

深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。一般用堆数据结构来辅助实现DFS算法。

深度优先遍历图算法步骤：

1.访问顶点v；

2.依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；

3.若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。

上述描述可能比较抽象，举个实例：

DFS在访问图中某一起始顶点v后，由v出发，访问它的任一邻接顶点w1；再从w1出发，访问与w1邻接但还没有访问过的顶点w2；然后再从w2出发，进行类似的访问，…如此进行下去，直至到达所有的邻接顶点都被访问过的顶点u为止。

接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。

七：BFS(广度优先搜索)

广度优先搜索算法（Breadth-First-Search），是一种图形搜索算法。简单的说，BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问，则算法中止。

BFS同样属于盲目搜索。一般用队列数据结构来辅助实现BFS算法。

1.首先将根节点放入队列中。

2.从队列中取出第一个节点，并检验它是否为目标。

如果找到目标，则结束搜寻并回传结果。

否则将它所有尚未检验过的直接子节点加入队列中。

3.若队列为空，表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。

4.重复步骤2。

八：Dijkstra算法

戴克斯特拉算法（Dijkstra’salgorithm）是由荷兰计算机科学家艾兹赫尔·戴克斯特拉提出。迪科斯彻算法使用了广度优先搜索解决非负权有向图的单源最短路径问题，算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。

该算法的输入包含了一个有权重的有向图G，以及G中的一个来源顶点S。我们以V表示G中所有顶点的集合。每一个图中的边，都是两个顶点所形成的有序元素对。(u,v)表示从顶点u到v有路径相连。我们以E表示G中所有边的集合，而边的权重则由权重函数w:E→[0,∞]定义。因此，w(u,v)就是从顶点u到顶点v的非负权重（weight）。边的权重可以想象成两个顶点之间的距离。任两点间路径的权重，就是该路径上所有边的权重总和。已知有V中有顶点s及t，Dijkstra算法可以找到s到t的最低权重路径(例如，最短路径)。这个算法也可以在一个图中，找到从一个顶点s到任何其他顶点的最短路径。对于不含负权的有向图，Dijkstra算法是目前已知的最快的单源最短路径算法。

1.初始时令S=,T=，T中顶点对应的距离值

若存在<V0,Vi>，d(V0,Vi)为<V0,Vi>弧上的权值

若不存在<V0,Vi>，d(V0,Vi)为∞

2.从T中选取一个其距离值为最小的顶点W且不在S中，加入S

3.对其余T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值缩短，则修改此距离值

重复上述步骤2、3，直到S中包含所有顶点，即W=Vi为止

九：动态规划算法

动态规划（Dynamicprogramming）是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。

动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

关于动态规划最经典的问题当属背包问题。

1.最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。

2.子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。

十：朴素贝叶斯分类算法

朴素贝叶斯分类算法是一种基于贝叶斯定理的简单概率分类算法。贝叶斯分类的基础是概率推理，就是在各种条件的存在不确定，仅知其出现概率的情况下，如何完成推理和决策任务。概率推理是与确定性推理相对应的。而朴素贝叶斯分类器是基于独立假设的，即假设样本每个特征与其他特征都不相关。

朴素贝叶斯分类器依靠精确的自然概率模型，在有监督学习的样本集中能获取得非常好的分类效果。在许多实际应用中，朴素贝叶斯模型参数估计使用最大似然估计方法，换言朴素贝叶斯模型能工作并没有用到贝叶斯概率或者任何贝叶斯模型。

尽管是带着这些朴素思想和过于简单化的假设，但朴素贝叶斯分类器在很多复杂的现实情形中仍能够取得相当好的效果。

通过掌握以上算法，能够帮你迅速提高编程能力，成为一名优秀的程序员。