winbobob的专栏

虽然是一些最最基本的概念，理顺的感觉还是ma'nv

为什么选择跳跃表目前经常使用的平衡数据结构有：B树，红黑树，AVL树，Splay Tree, Treep等。 想象一下，给你一张草稿纸，一只笔，一个编辑器，你能立即实现一颗红黑树，或者AVL树出来吗？ 很难吧，这需要时间，要考虑很多细节，要参考一堆算法与数据结构之类的树，还要参考网上的代码，相当麻烦。 用跳跃表吧，跳跃表是一种随机化的数据结构

Floyd算法1.定义概览Floyd-Warshall算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。Floyd-Warshall算法的时间复杂度为O(N3)，空间复杂度为O(N2)。 2.算法描述1)算法思想原理：     Flo

Dijkstra算法是处理单源最短路径的有效算法，但它局限于边的权值非负的情况，若图中出现权值为负的边，Dijkstra算法就会失效，求出的最短路径就可能是错的。这时候，就需要使用其他的算法来求解最短路径，Bellman-Ford算法就是其中最常用的一个。该算法由美国数学家理查德•贝尔曼（Richard Bellman, 动态规划的提出者）和小莱斯特•福特（Lester Ford）发明。Bel

图邻接矩阵表示1．图的邻接矩阵表示法　 在图的邻接矩阵表示法中：　 ① 用邻接矩阵表示顶点间的相邻关系　 ② 用一个顺序表来存储顶点信息2．图的邻接矩阵(Adacency Matrix)　 设G=(V，E)是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵：【例】下图中无向图G 5 和有向图G 6 的邻接矩阵分别为A l 和A 2 。3．网络的邻

键集合 U 包含 n 个键，哈希表 T 包含 m 个槽，集合 H 包含一些哈希函数。如果 H 满足：对于任意 x, y ∈ U,  集合 { h | h∈H && h(x) = h(y) } 的元素个数等于 |H|/m，则称 H 为全域哈希；对全域哈希 H，从 H 中随机选择哈希函数，任意键 x, y 冲突概率等于 1/m；对于全域哈希 H，从中随机选择 h 作为哈希函数，对任意的键 x，与他

网上关于树的各种名称各种各样，平衡搜索树，

binary search tree，中文翻译为二叉搜索树、二叉查找树或者二叉排序树。简称为BST一：二叉搜索树的定义他的定义与树的定义是类似的，也是一个递归的定义：1、要么是一棵空树2、如果不为空，那么其左子树节点的值都小于根节点的值；右子树节点的值都大于根节点的值3、其左右子树也是二叉搜索树在算法导论中的定义：下图中是BST的两个

为什么要把计数排序(Counting Sort)、基数排序(Radix Sort)和桶排序(Bucket Sort)

堆排序与快速排序，归并排序一样都是时间复杂度为O(N*logN)的几种常见排序方法。学习堆排序前，先讲解下什么是数据结构中的二叉堆。二叉堆的定义二叉堆是完全二叉树或者是近似完全二叉树。二叉堆满足二个特性：1．父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值。2．每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。当父结点的键值总

缓存算法发表于 2011-10-28　　原文：http://www.jtraining.com/component/content/article/35-jtraining-blog/98.html　　翻译：http://www.zavakid.com/25引言　　我们都听过 cache，当你问他们是什么是缓存的时候，他们会给你一个完美的答案，可是他们不

有两种常用的方法可用来搜索图：即深度优先搜索和广度优先搜索。它们最终都会到达所有连通的顶点。深度优先搜索通过栈来实现，而广度优先搜索通过队列来实现。  深度优先搜索：下面图中的数字显示了深度优先搜索顶点被访问的顺序。为了实现深度优先搜索，首先选择一个起始顶点并需要遵守三个规则：(1) 如果可能，访问一个邻接的未访问顶点，标记它，并把它放入栈中。(2) 当不能执行

在c++中，vector是一个十分有用的容器，下面对这个容器做一下总结。1 基本操作(1)头文件#include.(2)创建vector对象，vector vec;(3)尾部插入数字：vec.push_back(a);(4)使用下标访问元素，cout(5)使用迭代器访问元素.vectorint>::iterator it;for(it=ve

为什么选择跳表目前经常使用的平衡数据结构有：B树，红黑树，AVL树，Splay Tree, Treep等。 想象一下，给你一张草稿纸，一只笔，一个编辑器，你能立即实现一颗红黑树，或者AVL树出来吗？ 很难吧，这需要时间，要考虑很多细节，要参考一堆算法与数据结构之类的树，还要参考网上的代码，相当麻烦。 用跳表吧，跳表是一种随机化的数据结构，目前

澄清P问题、NP问题、NPC问题的概念这或许是众多OIer最大的误区之一。    你会经常看到网上出现“这怎么做，这不是NP问题吗”、“这个只有搜了，这已经被证明是NP问题了”之类的话。你要知道，大多数人此时所说的NP问题其实都是指的NPC问题。他们没有搞清楚NP问题和NPC问题的概念。NP问题并不是那种“只有搜才行”的问题，NPC问题才是。好，行了，基本上这个误解已经被澄清了。下面的内容

今天在网上看到一个讲动态规划的文章，是以01背包为例的，这文章和书上的讲解非常不一样，令我眼前一亮，于是转载一下下～～～（说明一下，本人非常痛恨教材公式定理漫天飞，实际的讲解却讲得非常枯涩难懂，这种中国式的教育已经延绵了几千年了，现在中国的教材还是这个样子，讲清楚些明白些就那么难么？高中有个老师讲的一句话一直觉得很有道理：“教得会天才不是真本事，能把博士生的东西讲到小学生都会用那才是真水平。”

Dijkstra算法1.定义概览Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。注意该算法要求图中不存在负权边。问题描述：在无向图 G=(V,

前几天在看Floyd算法的时候，虽然感觉程序很简单，但是让你动手写那些过程矩阵的时候就感觉不怎么简单了，就上网找找看有木有简便的计算方法，搜索之后没有发现有现成的例子，只搜到了两句“弄两条线，从左上角挪到右下角”，“十字交叉法，从左上角到右下角”，除此之外就再也木有找到有用的东西了，既然没有现成的就自己根据这两句来吧，于是就有了下面的这篇。。。。。。下面的纯属个人见解，如有不正确的还请大家

和MIT算法导论课上讲的类似，多了具体的代码实现~~

Up to this point we have been consideringalgorithms deterministically, i.e. best and worst case behavior. Wehave occasionally looked at average case behavior, but assumed that all inputsare equally li

Strassen的矩阵乘法算法虽然时间复杂度为

#include#includevoid Merge(int a[],int p,int q,int r){ int n1=q-p+1; int n2=r-q; int *L=(int *)malloc(sizeof(int)*(n1)); int *R=(int *)malloc(sizeof(int)*(n2)); for(int i=0;i<n1;i++) //

Horner's Rule for PolynomialsA general polynomial of degree  can be written as (1)If we use the Newton-Raphson method for finding roots of the polynomial we need to eva

在算法导论中 Iterated Logarithm Function是在Functional iteration

最大子树问题（The maximum-subarray problem）这是最大子树问题 Θ(nlgn) 的C语言实现代码

http://blog.csdn.net/tangl_99/article/details/771089MIT的算法导论第一节课上，教授就说得了算法的performance的重要性，并非简单的只是快一点，慢一点，而是整个解决方案可行与不可行的差别。作为一个学生来说，在《算法导论》和《计算机程序设计艺术》两本最经典书来说，应该选择《算法导论》来读，这样读起来更加容易。如果我还能回到刚入大

偏序只对部分元素成立关系R，全序对集合中任意两个元素都有关系R。例如：集合的包含关系就是半序，也就是偏序，因为两个集合可以互不包含；而实数中的大小关系是全序，两个实数必有一个大于等于另一个；又如：复数中的大小就是半序，虚数不能比较大小。

http://www.cnblogs.com/xuxu8511/archive/2012/08/15/2640378.html解法很简单，但是yao'xiang'dao

算法导论习题5.2.4介绍了一个帽子保管问题(hat-check problem)：有n位顾客，他们每个人给餐厅负责保管帽子的服务生一顶帽子。服务生以随机的顺序将帽子归还给顾客。请问拿到自己帽子的顾客的期望数目是多少？解法一：利用算法导论一书中介绍的indicator random variables，假设随机变量Xi满足(1  那么总的随机变量x满足：

斯特林公式（Stirling's approximation）是一条用来取n的阶乘的近似值的数学公式。一般来说，当n很大的时候，n阶乘的计算量十分大，所以斯特林公式十分好用，而且，即使在n很小的时候，斯特林公式的取值已经十分准确。

贪心算法的设计思想         贪心算法在解决问题的策略上目光短浅，只根据当前已有的信息就做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。换言之，贪心法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。贪心算法对于大部分的优化问题都能产生最优解，但不能总获得整体最优解，通常可以获得近似最优解。引例 [找零钱]一个小孩买了价值少于1美元的糖，并

极好的一篇文章， 作者：July、weedge、Frankie。编程艺术室出品。说明：本文从B树开始谈起，然后论述B+树、B*树，最后谈到R 树。其中B树、B+树及B*树部分由weedge完成，R 树部分由Frankie完成，全文最终由July统稿修订完成。出处：http://blog.csdn.net/v_JULY_v 。 第一节、B树、B+树、B*树1.前言：动

An algorithm for a computational problem is a computational method, a procedure, that takes in the inputs and spits out an output that obeys the mathematical relation defined in the computational prob

一直不知道差分约束是什么类型题目，最近在写最短路问题就顺带看了下，原来就是给出一些形如x-y好神奇的是这类问题竟然可以转换成图论里的最短路径问题，下面开始详细介绍下比如给出三个不等式,b-a由题我们可以得知，这个有向图中，由题b-a根据以上的解法，我们可能会猜到求解过程实际就是求从a到c的最短路径，没错的....简单的说就是从a到c沿着某条路径后把所有权值和

1、P(polynomial)问题      可以在以多项式表达的时间内按部就班的按照步骤求出确切解的问题，也就是说它的计算复杂度是一个多项式。我们通常用的O(n),O(logn),O（n2）等等类似的都是这类问题。2、NP（Non-deterministicPolynomial）问题      有些计算问题是确定性的，比如加减乘除之类，你只要按照公式推导，按部