以下是为您整理出来关于【算法导论】合集内容，如果觉得还不错，请帮忙转发推荐。
---恢复内容开始---5.1-1证明：假设在程序HIRE-ASSISTANT的第4行中，我们总是能够决定哪一个应聘者最佳，则意味着我们知道应聘者排名的总次序 既然我们总是能够决定哪一个应聘者最佳，想必我们已经对应聘者进行比较了，既然已经进行比较，排序就不应是个问题，既然可以进行排序，总次序也就可以知道了5.1-2描述RANDOM(a,b)过程的一种实现，它只调用RANDOM(0,1)。作为a和b的函数，你的程序的期望运行时间是多少？ 没看懂，不会...
class Graph:def__init__(self):self.V = []class Vertex:def__init__(self, x):self.key = xself.color = ‘white‘self.d = 10000self.f = 10000self.pi = Noneself.adj = []self.next = Noneclass Solution:def Dfs(self, G):for u in G.V:u.color = ‘white‘u.pi = Noneglobal timetime = 0for u in G.V:if u.color == ‘white‘:self.DfsVisit(G, u)def DfsVisit(self, G, u):global timetime = time + 1u.d = timeu.color =...
1、概念二叉搜索树性质：设x是二叉搜索树的一个节点，那么：a) 对x左子树中任意节点y, y.key < x.keyb) 对x右子树种任意节点y, y.key >= x.key 2、数据结构 1struct TreeNode2{3 TreeNode(int key): left(NULL), right(NULL), parent(NULL), key(key) {};4 TreeNode* left;5 TreeNode* right;6 TreeNode* parent;7int key;8};910class Tree 11{ 12public: 13 Tree(): m_root(NULL) {}; 14 TreeNode* minimu...
设有n=2k个选手参加比赛，要求设计一个满足一下要求的比赛日程表:（1）每个选手必须与其他的n-1个选手个比赛一次；（2）每个选手每天只能赛一次 。 按此要求可以把比赛日程表设计成一个n行n-1列的二维表，其中第i行第j列表示第i个选手在 第j天比赛的选手。 代码：（分治策略） 1 #include<stdio.h>2 #include<math.h>3 4void gametable(int k)5{6int a[100][100];7int n,temp,i,j,p,t;8 n=2;//k=0两个参赛选手日程可以直接求得...
堆数据结构是一种数组对象，它可以被视为一颗完全二叉树，树中每个节点和数组中存放该节点值的那个元 素对应。如果表示堆的数组为A，那么树的根为A[1]。一、 堆1. 表示堆的数组A是一个具有两个属性的对象：length(A)是数组中的元素个数，heap-size(A)是存放在A中的堆的元素个数；A[heap-size(A)]之后的元素都不属于相应的堆。也就是：Heap-size(A)<=length(A)。2. 给定某个节点的下标i，其父节点PARENT(i)，左儿子LEFT(i)和右儿子R...
12.3-1 二叉搜索树insert操作的递归版本void insert1(Node* pRoot, Node* pAdd) {bool bLeft = pAdd->key < pRoot->key;Node* pNextRoot = bLeft ? pRoot->left : pRoot->right;if(pNextRoot)insert1(pNextRoot, pAdd);else{pAdd->parent = pRoot;if(bLeft)pRoot->left = pAdd;elsepRoot->right = pAdd;} } 12.3-2 insert过程途经n个节点后遇到了空节点，便将待插入的元素安放上去了，接下来的search过程先路过同样的n个节点，最后...
题目：对于一棵有N个结点的树，设计在O(N)时间内完成的先序、中序与后序遍历算法 一、先序遍历递归实现：void InOrder( SearchTree T ) {if ( T != NULL ){Visit( T );InOrder( T->Left );InOrder( T->Right );} }非递归实现：版本一：栈模拟（深度优先搜索）void PreOrder( SearchTree T ) {Stack S;while( T != NULL || !S.Empty() ){if ( T != NULL ){S.push( T );Visit( T );T = T->Left; }else{T = S.pop();T = T->Right;}} ...
原文请参考：http://www.cnblogs.com/Anker/archive/2013/01/22/2872261.html本章介绍了算法分析中的渐进分析符号，几个重要渐进记号的定义如下：Θ(g(n))={ f(n): 存在正常数c1,c2和n0，使对所有的n>=n0，有0<=c1g(n)<=f(n)<=c2g(n) }O(g(n))={ f(n): 存在正常数c和n0，使对所有n>=n0，有0<=f(n)<=cg(n) }Ω(g(n))={ f(n): 存在正常数c和n0，使对所有n>=n0，有0<=cg(n)<=f(n) }o(g(n))={ f(n): 对任意正常数c，存在常数n0>0，使对...
斐波拉契堆是由一组最小堆有序树组成，每棵树遵循最小堆性质，并且每棵树都是有根而无序的。所有树的根通过left和right指针来形成一个环形的双链表，称为该堆的根表。 对于一个给定的斐波拉契堆H ，可以通过指向包含最小关键字的树根指针H.min来访问。堆中每个节点还包含x.mark,x.degree两个域，x.degree表示x的子女表中的子女个数；x.mark表示从x上次成为另一个节点子女以来是否失掉一个孩子。斐波拉契对的结构如下：势能函数：...
主定理常用于计算递推式的时间复杂度。 原文：http://www.cnblogs.com/jdflyfly/p/3954637.html