最长子序列和

最长子序列和 给定一组正数，需要求出这组数字中子序列之和最大值，当然这个子序列得是连续的，不然只需要把所有正数找出来求和即可。 比如： 序列：-2 11 -4 13 -5 -2，则最大子序列和为20； 序列：-6 2 4 -7 5 3 2 -1 6 -9 10 -2，则最大子序列

Apr 19 2015

算法（6）线性规划介绍

算法（6）线性规划介绍 线性规划 在线性规划的问题中，给定一组变量，我们希望能够给这些变量赋值使得它们可以满足下面两个条件：1. 变量满足一组线性等式或者线性不等式； 2. 对线性目标函数（linear objective function）得到它的最大值或者最小值。 这样讲比较

Apr 12 2015

最长公共子串&最长公共子序列

最长公共子串&最长公共子序列 我们经常需要计算两个字符串的公共部分，也就是子字符串，这时候子字符串的连续性将是我们区分问题的关键点。如果它是连续的，我们要求的是最长公共子串（Longest Common Substring）；如果它不需要连续，我们求得是最长公共子序列（Longe

Apr 9 2015

最长递增子序列

最长递增子序列 描述 所谓最长递增子序列表示在给定数字序列a1,a2,...,an中，有这么一组子序列ai1,ai2,...,aij，它们满足ai1<ai2<…<aij，它们的下标满足i1<i2<…<ij。我们称这样的序列是自增子序列，那么我们

Mar 24 2015

算法（4）运用动态规划来处理NPC问题

算法（4）运用动态规划来处理NPC问题 在之前的课程中，我们提到了很多困难问题，也对这些困难问题进行描述，但是我们并没有提到如何解这些问题。这次我们将利用动态规划（Dynamic Programming）来解决一些之前课程中提到的问题。这里有个小插曲：动态规划的英文是Dynami

Mar 24 2015

社交网络中的中心性

社交网络中的中心性 在社交网络分析中常常会用到中心性(Centrality)这个概念，有时候经常会遇到好多XXX Centrality，首先中文意思难翻译，其次感觉意思都差不多啊。最近因为实验室的研究，所以特地整理了一下。首先在中心性的分析角度上有两种出发点：中心度和中心势。 中

Mar 16 2015

最短路径

最短路径 除了遍历以外，对图最常见的操作就是求点到点的最短路径了。在日常生活中，这个问题也十分常见，比如我从宿舍出发，要去游泳馆，那么我得计划一条去游泳馆最近的路线，宿舍和游泳池可以看作图的节点，到游泳池的路上经过个个节点的路程长度看作是边的权值。在地图中，这个应用更为广泛，一个

Mar 14 2015

欧拉路径&欧拉环

欧拉路径&欧拉环 欧拉路径表示从图中一点出发，经过图中所有的边，且只经过一次。而欧拉回路表示之前的路径，起点与终点是同一个点。 这里就简单列一下他们的性质： 图中存在欧拉回路当且仅当每个顶点都有偶数度； 图中存在欧拉路径当且进度图中至多两个顶点是奇数度。 一般求解欧拉问题，都

Mar 14 2015

最小生成树

最小生成树 问题的描述 在日常生活中，我们会遇到这样的问题：在我们面前有几台电脑，需要我们使用网线将他们连起来，但是我们手头的网线长度有限，而且电脑很重不方便挪动，那么有什么办法可以利用最少的网线来将这些电脑都连起来呢？将这个问题抽象一下就得到了求最小生成树(Minimum sp

Mar 12 2015

友情链接

友情链接 在$THEME/layout/_widget中创建links.ejs 将下面的如何复制进links.ejs中： 12345678910<div class="linkslist"> <p class="asidetitle"><%

Mar 11 2015

算法（2） 有效问题&困难问题

算法（2） 有效问题&困难问题 第二节算法课，内容很广，涉及了很多的问题，但是老师都没有详细展开，这给我课余学习和写博客提供了很多的素材啊！在本科学习中，我们学到的问题基本都是有高效的算法可以解决，但实际上还有很多问题是暂时没有找到高效算法，在多项式时间内无法求解。这堂课就是对这

Mar 11 2015

求有向无圈图的拓扑序列

求有向无圈图的拓扑序列 问题的描述拓扑序列表示一组图中节点的列表，序列中的每个节点必须满足这样的条件：如果边(s,t)在图中（s为源节点，t为汇节点），那么点s在序列中的位置在t位置之前。 根据上面的条件，我们可以得到这样2个结论： 这个图必须得是有向无权图（DAG），不然s

Mar 9 2015

第K小的数和中位数

第K小的数和中位数 在一组有序数列中，如果数列大小是偶数，那么它的中位数是中间两数之和的一半；如果数列大小是奇数，那么它的中位数自然就是最中间的那个数。根据上面的定义，要得到有序数列的中位数，可以直接访问，复杂度是O(1)。 那如果给我们的数列是无序的呢？针对这个问题，我们可以再

Mar 8 2015

编辑距离

编辑距离 我们都用过在线字典，应该会有这样一个体验：在输入我们想要单词的前几个字母时，输入框下的提示框会给我们推荐若干个字母相近的单词。或者另一种用户体验：拼写检查。那么这些单词推荐是怎么实现的呢？程序是怎么知道我们想要的单词的呢？这里就需要引入编辑距离(Edit distanc

Mar 4 2015

Is log(n!) = Θ(n·log(n))？

Is log(n!) = Θ(n·log(n))？ 在上算法课的时候，老师给我们做了个quiz，题目是f(n)=ln(n!)和g(n)=nlog(n)的关系。 当然根据解题经验来说，ln(n!) = Θ(n·log(n))，那么怎么证明它是对的呢？ 首先利用换底公式可以将ln换成

Mar 4 2015