算法的基础

1. 算法基础之大O表示法

    大O表示法是一种特殊的表示法，其用来 指出算法的速度有多块

    注意：大O表示法指出了最糟糕情况下的运行时间

    1：对于普通的简单查找算法，如果有100个元素，最多需要猜测100次，如果有40亿个元素，最多需要40亿次，即最多需要猜测的次数与元素的个数成正比，被称为 线性时间 ，即：O(n)

    2：对于二分查找算法，100个元素最多需要猜测7次，而40亿的元素也仅仅最多需猜测32次，其运行时间为 对数时间 ，即：O(logN)

    下面做一个算法执行时间增速的实验：

    采用简单的查找算法，我们知道，随着所需要查找元素个数的递增，所需要的时间也是呈线性递增的。

    而对于二分查找，其随着查找元素的递增，所需要的查找时间的增速是很缓慢的。（ 摘自算法简介 ）

大O表示法指出了算法有多块，其并没有单位，即并非是指以秒为单位的，大O表示法让你能够比较操作数，用来指出算法运行时间的增速。

    简单查询算法用大O表示法：O(N)

    二分查找算法用大O表示法：O(logN)

    N表示的是操作数

    综上所述，我们知道了算法的速度指的并非时间，而是操作数的增速。在谈论算法的速度时，我们说的是随着输入数的增加，其运行时间将会以什么样的速度增加。

    在计算机领域中有一个非常着名的旅行商的问题，其计算时间增加的非常快。

    简介：有一位旅行商，需要前往5个城市，同时要保证旅程最短，故可考虑前往这些城市的所有可能顺序，对于每一种顺序，都计算出总旅程，再挑选出旅程最短的路线，5个城市就会有120种不同的排列方式。即5个城市需要120次操作，涉及6个城市时，需要720次操作，7个城市时，需要5040次操作。

    综上涉及到n个城市时，需要执行n!（n的阶乘）次操作才能计算出最终需要的最短旅程路线。用大O表示法为O(N!)，即 阶乘时间。

如果涉及的城市数量过多，会造成计算出结果时，太阳已经下山了...

2. 算法的基本要素有哪些

算法通常由两种基本要素组成分别是对数据对象的运算和操作；算法的控制结构，即运算或操作间的顺序。
算法是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。算法中的指令描述的是一个计算，当其运行时能从一个初始状态和（可能为空的）初始输入开始，经过一系列有限而清晰定义的状态，最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。随机化算法在内的一些算法，包含了一些随机输入。

3. 程序员开发用到的十大基本算法

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

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

算法步骤：
1 从数列中挑出一个元素，称为 “基准”（pivot），
2 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

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

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

算法步骤：
1.创建一个堆H[0..n-1]
2.把堆首（最大值）和堆尾互换
3.把堆的尺寸缩小1，并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置
4.重复步骤2，直到堆的尺寸为1

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

算法步骤：

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

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

算法步骤：

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

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

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

算法步骤：

上述描述可能比较抽象，举个实例：
DFS 在访问图中某一起始顶点 v 后，由 v 出发，访问它的任一邻接顶点 w1；再从 w1 出发，访问与 w1邻 接但还没有访问过的顶点 w2；然后再从 w2 出发，进行类似的访问，… 如此进行下去，直至到达所有的邻接顶点都被访问过的顶点 u 为止。

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

算法七：BFS(广度优先搜索)
广度优先搜索算法（Breadth-First-Search），是一种图形搜索算法。简单的说，BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问，则算法中止。BFS同样属于盲目搜索。一般用队列数据结构来辅助实现BFS算法。

算法步骤：

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

该算法的输入包含了一个有权重的有向图 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算法是目前已知的最快的单源最短路径算法。

算法步骤：

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

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

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

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

算法步骤：

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

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

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

4. 算法基础知识（全连接层、LSTM、激励函数）

1、全连接层作用：

全连接的一个作用是维度变换，尤其是可以把高维变到低维，同时把有用的信息保留下来。

全连接另一个作用是隐含语义的表达(embedding)，把原始特征映射到各个隐语义节点(hidden node)。对于最后一层全连接而言，就是分类的显示表达

2、简述LSTM如何解决梯度消失

LSTM有能力向单元状态中移除或添加信息，通过门结构来管理，包括“遗忘门”，“输出门”，“输入门”。通过门让信息选择性通过，来去除或增加信息到细胞状态. 模块中sigmoid层输出0到1之间的数字，描述了每个成分应该通过门限的程度。0表示“不让任何成分通过”，而1表示“让所有成分通过！

一个对RNN和LSTM分析比较好的连接 （注意理解体会一下他说的公式）

3、激励函数：

作者这篇激励函数写的也很好 （我们实际中一般遇见都是非线性问题，所以对特征做了加权线性操作需要通过非线性的激励函数做非线性的变换）

激励函数选择

4、BP的反向推导（ 详细参考 ）（ 参考2 ）

5. 算法基础

谨以此文，感谢我在这个学校最喜欢的两个老师之一——肖my老师。本文基本为老师上课说讲授内容加上一部分自己的感悟拼凑而来，写作文本的目的是为自己的算法课程留下一点点东西，站在老师肩膀上形成粗糙的框架，方便以后的复习以及深入。文笔有限，其中包含的错误还请多多包容，不吝赐教。

to do list：

时间复杂度中递归树法；动规，分治新的感悟；

点覆盖：一组点的集合，使得图中所有边都至少与该集合中一个点相连。

支配集：一组点的集合，使得图中所有的点要么属于该集合，要么与该集合相连。

最大团：在一个无向图中找出点数最多的完全图。

独立集：一组点的集合，集合中的顶点两两不相邻。（团转过来）

SAT问题：也称布尔可满足性问题。给一组变

其中Ci被称为句子。

点覆盖<->独立集<->最大团

最小割：割是一组边集。如s-t割就是如果去掉这些边，将把原图划分为两个点集，其中一个点集包含s，一个点集包含t。（两个是指不相连，而不是代表不存在边相连，如反向边）

decision problem: 是否存在。

search problem:找到一个解。

（这个还能扩展，比如decision problem在多项式时间内解决，所以他是P问题吗）

渐进符号：

注意以上三种都是紧的，对应的两个小写的符号是不紧的，即如下图所示：

概念：算法的时间复杂度是一个函数，用于定性描述算法的运行时间。注意，这个一个代表算法输入字符串长度的函数。

[注]输入字符串长度是一个比较关键的理解，比如在背包问题中，其时间复杂度为O(nW)，因为W不定，所以只能是一个伪多项式时间。

比较：c < log2N < n < n * Log2N < n^2 < n^3 < 2^n < 3^n < n! < n^n

大致：常数<对数<幂函数<指数函数<阶乘

对于指数是n相关的进行比较，优先比较指数，再比较底数。

记住一个特例：n ^(logn)<n!<n n

计算：

一般来说，计算采用主方法和递归树法，其中递归树技巧性比较强，主方法其实也是递归树推导归纳而来，且主方法能得到一个比较紧的结果。

主方法：

f(n) = af(n-b)+g(n) =>O( a^(n/b) *g(n) )

P：decision problems有一个多项式算法。

NP（nondeterministic polynomial-time）：decision problems能够在多项式时间内验证。

NPC：NP完全问题，首先这个问题是NP的，其次，其他所有问题都可以多项式时间内归约到它。

NPH：如果所有NP问题都可以多项式时间归约到某个问题，则称该问题为NP困难。

因为NP困难问题未必可以在多项式时间内验证一个解的正确性（即不一定是NP问题），因此即使NP完全问题有多项式时间的解（P=NP），NP困难问题依然可能没有多项式时间的解。因此NP困难问题“至少与NP完全问题一样难”。

一些NP问题能在多项式时间内解决，因为 P∈NP

NP难类型问题的证明：

先选好一个已知NP难的问题，然后将已知NP难问题多项式归约到要证明的问题上。先给出这个归约，然后再证明这个归约的正确性。

NPC类型问题的证明：

证明一个问题Y是NPC问题，先说明Y是NP的，然后找到一个NPC问题X，将这个问题X归约到问题Y上，即证明完成。

常见的NPC问题（重要，规约的时候有用！）：

packing problems: set-packing，独立集

覆盖问题：集合覆盖问题，顶点覆盖问题

严格满足问题(constraint satisfaction problems)：SAT，3SAT

序列问题：哈密尔顿回路，旅行商问题

划分问题：3D-matching, 3着色问题

数字问题：子集合问题（子集元素之和为t），背包问题

其他：分团问题（是否存在一个规模为k的团）

规约的概念与理解

规约：意味着对问题进行转换，例如将一个未知的问题转换成我们能够解决的问题，转换的过程可能涉及到对问题的输入输出的转换。

自归约：search problem <=p decision problem

归约：A归约到B，也就是说，我们对A套一个函数f，在f函数的作用下形成一个新的问题，对这个问题运用B的黑盒解法，能够解决问题A。

(B <=p A)一般说来，B问题如果可以归约到A问题，也就是说，一个解决A问题的算法可以被用做子函数（子程序）来解决B问题，也就是说，求解B问题不会比求解A问题更困难。因此，如果B问题是困难的，那么A问题也就是困难的，因为不存在求解A问题的高效算法。(最后一句不懂)

我简单说一下我理解的规约，以X规约到Y为准，大概分成两个方面：

注：在 三 的一些实例中细品。

概念：在对问题求解时，总是做出在当前看来是最好的选择。

贪心的证明：先假设贪心算法得到的解不是最优解，假设S1是贪心算法得到的解，而S2是所有最优解中和S1具有最多相同元素的解，然后比较S1和S2，观察S1和S2中第一个（最前面一个）不一样的元素，然后在贪心解S2中将不一样的元素换成S1中的那个元素得到另一个最优解S3，这样S3和S1比S2和S1有更多相同元素，和假设S2是与S1有最多相同元素的最优解矛盾，这样来推导S1是最优解。

我的理解：假设这个不是最优的，但是一定存在一个最优的解在某一个位置之前和我当前解结构是一样的，那么在这个位置，选最优解也可以选当前解，不影响最终答案。

[注]概念很简单，但是实际操作的时候，贪心的角度很重要，同样的贪心，方向对了，算法就是对的。

例子：

给你一系列活动，每个活动有一个起始时间和一个结束时间，要求在活动不冲突的情况下找到一种有最多活动的安排。

对于这个问题，我们有一下几种贪心的角度：

①将任务按照 开始时间 升序排列。

②将任务按照 结束时间 升序排列。

③将任务按照 任务时长 升序排列。

④对于每一个任务，都记录与其他任务冲突的数量，按照 冲突数量 的升序排列。

其中1，3，4都是不可以的。

任务结束时间的贪心证明（反证法）：

假设贪心不是最最优的，那我们在最优解中找一个与当前解有最相似的解。

由图可以知道，贪心贪的就是最早结束，所以如果不是最优，那么最优的结束时间一定晚于贪心的结束时间。

由上图就可以证明。

最大流通常与最小割相联系。

f 为任意一个流，cap为容量，对于任意的s-t割出来的点集（A，B），v( f ) <= cap(A, B)。

当流增加到与割的容量相等时候，就不可能再有增长空间了，称为最大流。

对于割的容量来说，不同的割法会有不同流量，有些割法永远不会有流达到，比如部分A = {s}, B = {V - s}，这种把源点割出来的割法。

综上，通过这种感性的认识，如果能找到一个最小的割，那么这个割就一定是最大能跑到的流（如果流能更高的话在这个割上就会超过容量，反证。）

上图为一条增广路，一条增广路即为一条s-t的路径，在路径上仍有流可以跑，其曾广的流就是该条路径上最小的剩余容量。（相当于每找一条增广路，就至少有一条边达到满流。）

直到在图中找不到增广路，此时已经达到了最大流。

找ST集合：把满流的边去掉，从S出发走到能到的点，遍历的点就是S集合；剩下的点就属于T集合。注意，如果找到了在找S集合的时候找到了T点，说明还可以继续找增广路。

[补]有一个很有趣的延伸，如多源点多终点问题。问：如果我有两个源点s1，s2，两个终点t1，t2，我想求一组流，使得s1-t1，s2-t2的流达到最大，是否可以加一个源点S，S与s1，s2相连，边流无限大；加一个终点T，T与t1，t2相连，边流无限大，然后这组ST的最大流即可。——答案是No，无法保证是s1-t1，s2-t2，有可能交错。

例子讲的感觉不是特别好，对理解感觉起不到很大作用，希望以后有新的想法后进行补充。

规约是一个重要的概念和思想。

一个图的 最大独立集 与 最小点覆盖 是不相交的两个点集，它们的并就是整个点集。

个人理解：独立集和点覆盖都是从点的角度进行划分的，如果我们从边的角度来看，①一个最小的点覆盖即为我集合中的每一个点都尽可能与更多的边相连，②同时，一条边的两个端点中，只能有一个端点在最小点覆盖中[下注]

[注]我们假设有一条边两个端点（u，v）都在点覆盖之中，首先显然u，v都不是端点，因为假设u是端点的话只需要选择v即可；

给一个集合S和一堆S的子集S1，S2，...，Sm，问是否存在存在k个子集，使它们的并集为S。

构造：

集合为点，集合中的元素为边，有相同元素的边相连。（注意如果某一元素只在一个子集中出现，应该怎么处理呢！）

规约：在构造的图中找最小的点覆盖，选中的点能覆盖所有的边即为对应集合的并集能包含所有的元素。所以就完成了集合覆盖到点覆盖的规约。

构造：每个句子构造一个三角形，把对应变量但是相反取值的点相连。

规约：3SAT的有一个特点就是，每一个句子中至少有一个为真即可，每个句子都必须是真。将相同变量相反取值相连的目的就是，在最大独立集中，比如选择x为真，则剩下所有句子中x-ba一定不会被选中，同时由独立集和构造出来三角形的性质可以知道，每一个句子，有且仅有一个会被选中（为真）。如上图，x1-ba为真，x2-ba和x3任选一个为真即可满足。

search problem <=p decision version

比如：如果能在多项式时间内找到一个哈密尔顿圈，那么就能在多项式时间内找到一个哈密尔顿圈（删边）

在此再谈P和NP：

我们知道有些问题是可以从搜索问题规约到判断问题的，也就是所该问题如果能在多项式内判断，那么久能在多项式中搜索到，那么我们只需要说，这个判断问题能在多项式时间内求解，就叫做P问题，也就是上图红字的意思；那NP问题呢，必须要给出一个解的实例，判断的是这个实例是否满足求解问题，这个才是上图中的红字。比如，我如果能在多项式时间内判断哈密尔顿圈是否（Yes/No）存在，那这个就是ploy-time algorithm，如果我给出了一系列点，能过多项式时间内判断这些点能否构成哈密尔顿圈，那这个就是poly-time certifier。

构造：把一个点拆分成三个点。

构造：（下面两个图要连在一起看）

从行的角度看，一行代表一个变量；从列的角度来看，每三列代表一个句子。两边中一边是两个点，一边是一个点，所以有k个句子的话，每一行有3k+3个节点。从哈密尔顿圈的答案转到3SAT的答案看这个圈在每一行是从左到右还是从右到左。

子集和问题：给一个集合S，问是否能在集合中选取元素，使得总和为W。

构造：如下图，按照前六行和前三列进行分割，可以分成4部分，其中1,3,4部分是固定的，即在第一部分，变量v列和 变量为v（包括变量及取反）的行对应的格子为0，其余为0；第三部分全为0；第四部分按照12依次写下来。第二部分，如果Ci句子中有变量v，则记为1，因为一个句子只有三个变量，可以简单通过第二部分每一列和为3进行判定。此时集合已经构造出来，W为111444，与上面的规约相似，可以通过3SAT的简单性质进行感性的认知。

近似的想法很简单，要解决一个问题，我们希望能够做到①求解结果是最优的 ②在多项式时间内解决 ③对于任意的实例都能够通过该算法解决。现在对于部分问题，无法完全满足以上要求，所以就牺牲了①，但是我们希望结果不是盲目的，所以就引入了近似的概念。

近似算法。比如2-近似，认为W为近似解，W 为最优解，在求最小值的情况下W<=2W ；在求最大值的情况下，W>=1/2W*

给m个机器和n个任务，每个任务有一个ti的执行时间，我们认为完成最后一个任务所需的时间为负载时间，希望能够让这个负载时间最短。

第一种：将任务依次放在机器上，当某个机器空闲时立即放入新任务。此时是2近似的。

证明：

引理1.最短时间安排是大于等于任务中时间最长的任务，L* >= max tj

我们在考虑放入最后一个任务前，根据我们放置的规则，该机器是耗时最短，也就是说，该机器此时的用时是低于除掉最后一个任务后的平均时长，更低于所有任务的平均时长（引理2）；再根据引理1，最后一个任务应该是小于最优解的。

补充：

在这里，我还想讨论一下这个近似算法的中等于符号，先上结论：等号不一定能够找到一个实例，但是可以构造出一种结构，通过取极限求得，我们认为这样 也算是紧的。

构造实例：有m个机器，其中m(m-1)个任务的用时为1，1个任务的用时为m。肯定有一种任务集合，可以按照以下方式进行安排，此时的贪心解为19。

此时最佳的解为10，如下图：

通过推广可以知道此时的比为（2m-1）/m，当m取极限，能够达到2倍。

第二种：将任务从大到小排序，然后依次放在机器上，当某个机器空闲时立即放入新任务。此时是2近似的。

引理3：如果有大于m个任务，那么L*>=2t(m-1)。证明：t(m+1)是目前最短的任务，且目前所有机器上都有任务了，所以该任务加入时最优的情况不过是加入设备的原有任务刚好和t(m+1)相等，即等号。

（2近似）在n个点中，选取k个中心点，使得这些中心点能够以半径R的圆包含所有的点，让其中最大的半径最小，如下图所示：

基础：距离需要满足的三个定理①(同一性)dist(x, x) = 0 ②(自反)dist(x, y) = dist(y, x) ③(三角不等式)dist(x, y) <=dist(x, z)+dist(z, y)

r(C)为C集合中所有点的最大覆盖半径。（需要求min r(C)）

算法：在点集中任选一个作为中心点，然后重复以下步骤k-1次:选取距离已选点集中最远的点，加入点集。

证明：先假设r(C )< 1/2 * r(C)以选好的点画半径为1/2 * r(C)的圆，显然可知[注]，这个圆里有且仅有一个r(C )中的点。那么根据在下图中，根据三角不等式可以得出：

[注]在每个点上r(c )一定会包含到c点，而r(C )<1/2 * r(C)，相当于大圆套小圆，所以c*一定在c的圆中。

（2近似）问题还是很好理解的，在点上加权值，要找一个点覆盖，使得权值最小。如下图左边就是一个带权的最小点覆盖。

算法： 任选一条边(i, j)加上代价，这个代价从零开始，且这个代价的最大值低于i和j节点的权值。显然，这个边权值的最大值取决于两个端点权值的最小值，我们认为当边权值与点权值相等时，对应的那个点是紧的。把所有紧的点找出来即为点覆盖。

流程：

证明：

引理：边权之和小于等于点覆盖的点权之和。这主要是由于涉及到一条边上两个点都被选（紧的）的情况，感性认知可以看上图，缩放证明如下：

w(S)是等于所选的节点的权值之和的，等于所选节点节点所对应的边权之和，可以把它放大到所有节点对应边权之和，这样因为一条边(u, v)在u上算过一次后还要在v上算一次，所以等于边权和的两倍。再由上面引理可得。

主要为了线性规划和整数规划。

（2近似）没啥好说的，只需要把方程构造出来就行了。

由于求解出来结果不一定是整数，所以我们认为某一点的值大于1/2，就选入点集。

证明：

因为xi+xj >=1,且都是正数，那必至少一个点是大于1/2的（反证，两个都小于1/2则和小于1）。

给你n个物品和一个背包，每个物品有一个价值v和一个大小w，背包的容量是W，要求让背包装下尽可能大价值。

背包的时间复杂度：O(nW)

注意其中n表示物品的个数，无论是1个还是999个，他都是多项式的，这个很好理解。但是W就不一样了，这是一个数字。我理解的是这个数字会很奇特，比如1.00001，比如99999，这些有可能看起来不大但是实际在处理的时候很难处理的数字，统一的来说，如果我们把这些数字放在电脑上，都会以二进制的方式存储起来，有些数字用十进制表示很小，但是放在二进制上面就会很大，由W导致不能在多项式时间内解决（找不到一个范围/上界来框它）。

算法： 为了处理这个问题，我们改动了dp的状态转移方程，要让这个转移方程和W无关[注]。

此时还不是多项式的，然后我们再对value进行约。[注]

[注]这两步中，我们把w改成v，并对v进行近似处理。OPT的含义变成了，在面对是否选择第i个物品时，要想让价值达到当前值，最少的weight。理由是更改后的误差是可以忍受的：对v进行近似，结果只会出现最大价值的上下误差，如果对w进行近似，则有可能出现该物品不能放入背包中，导致整个物品直接放弃的情况。

6. 编程的基础算法有哪些

1、二叉树的每个结点至多只有二棵子树（不存在度大于2的结点），二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2^（i 1）个结点。

深度为k的二叉树至多有2^k 1个结点；对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0 = n2 + 1。二叉树算法常被用于实现二叉查找树和二叉堆。

递归算法能够解决的问题

数据的定义是按递归定义的。如Fibonacci函数。

问题解法按递归算法实现。如Hanoi问题。

数据的结构形式是按递归定义的。如二叉树、广义表等。

7. 数据结构与算法基础知识

1.数据结构的逻辑结构

(1)集合结构

(2)线性结构(存在唯一的第一个元素与唯一的最后一个元素)(eg: 线性表、队列、栈、字符串、数组、链表)

(3)树形结构(一对多)

(4)图形结构(多对多)

2.数据结构的物理(存储)结构

(1).顺序存储结构(插入与删除低效因为要挪动其他元素的位置。但是遍历简单)

(2).链式存储结构(插入与删除高效，但是遍历低效)

3.大O表示法(注意大O表示法表达的是最坏的情况)

规则：

(1)用常数1取代其他所有的常数(注意常数0也当1算)(3 -> 1, O(1))

(2) 只保留最高阶项(n^3+2n^2+5 ->n^3, O(n^3))

(3) 若存在最高阶，省略与其想成的常数(2n^3 -> n^3, O(n^3))

4. 时间复杂度类型

(1)常数阶

(2)线性阶

(3)平方阶

(4)对数阶

(5)立方阶

(6)nlog阶

(7)指数阶(O(2^n)或O(n!), 往往会造成噩梦般的时间消耗)

5. 空间复杂度(用大O表示法求解改算法的辅助空间即可，例如用于交换变量用的临时变量的数量)

六. 顺序存储的线性表

线性表结构特点：

(1) 存在唯一一个的被称作”第一个”的数据元素；

(2) 存在唯一一个的被称作”第二个”的数据元素；

(3) 除了第一个元素以外，结构中的每个数据元素均有一个前驱；

(4) 除了最后一个元素以外，结构中的每个数据元素均有一个后继。

七. 链式存储的线性表(单链表)

首元结点是链表中第一个值域不为空的结点。

头结点是一个值域为空且处于首位的结点。

首指针可指向首元结点也可指向头结点，但是如果指向头结点可以更加方便的处理单链表的插入和删除问题，不用再对首位做额外判断，并且指向头节点的指针永远不用变化。

*注意一下单链表的前插法和尾插法。尾插法更符合逻辑

8. 关于算法的基础知识

所谓解析法（analysis algorithm）是指用解析的方法找出表示问题的前提条件与结果之间关系的数学表达式，并通过表达式的计算来实现问题求解。
在实际问题中， 有些变量的取值被限定在一个有限的范围内。例如，一个星期内只有七天，一年只有十二个月， 一个班每周有六门课程等等。如果把这些量说明为整型， 字符型或其它类型显然是不妥当的。 为此，C语言提供了一种称为“枚举”的类型。在“枚举”类型的定义中列举出所有可能的取值， 被说明为该“枚举”类型的变量取值不能超过定义的范围。应该说明的是， 枚举类型是一种基本数据类型，而不是一种构造类型， 因为它不能再分解为任何基本类型。

9. 算法的基本结构是什么

算法的基本结构是顺序结构、条件分支结构、循环结构，顺序结构，是最简单的算法结构，语句与语句之间是按从上到下的顺序进行的。它是由若干个依次执行的处理步骤组成的，它也是任何一个算法都离不开的一种算法结构。

共同特点：

(1)只有一个入口和出口。

(2)结构内的每一部分都有机会被执行到，也就是说对每一个框来说都应当有一条从入口到出口的路径通过它，如图中的A，没有一条从入口到出口的路径通过它，就是不符合要求的算法结构。

(3)结构内不存在死循环，即无终止的循环。

顺序结构是最简单的算法结构，语句与语句之间是按从上到下的顺序进行的。它是由若干个依次执行的处理步骤组成的，它也是任何一个算法都离不开的一种算法结构。

如下算法是顺序结构的：

S1：m=a。

S2：a=b。

S1：b=m。

10. 算法设计基础

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]]