C++算法导论第九章O(n)期望选择序列第i小的数字
#include<iostream>#include<vector>#include<algorithm>#include<time.h>using namespace std;int randomized_partition(vector<in...
基于visual Studio2013解决算法导论之016查找最大值最小值
题目查找最大、最小值解决代码及点评#include <stdio.h>#include <stdlib.h>#include <malloc.h>#include <time.h>void PrintArr(int *pnArr, int nLe...
MIT:算法导论——5.线性时间排序:计数排序、基数排序以及桶排序
注:教材《算法导论》第8章 线性时间排序 一、决策树模型分析 排序算法下界 O(nlgn)定理:在坏情况下,任何比较排序算法都需要做Ω(nlgn)次比较。证明:对于一棵每个排列都是可达叶节点(l个)的决策树来说,树的高度(h)完全可以被确定。因为输入数据的n!种可能的排列都是叶节点,所以有n! &...
【算法导论】第8章线性时间排序_计数排序、基数排序、桶排序
1、问题引入 之前的堆排序、快速排序都是基于输入元素间的比较,这类排序叫做比较排序,对于n个元素的比较排序可以证明其在最坏情况下都要用O(nlgn)次比较来进行排序,本节中将讨论三种以线性时间运行的算法:计数排序、基数排序、桶排序,这些算法都用非比较的一些操作来确定排序顺序。 2、算法讨...
合并排序算法函数(算法导论)
#include "stdafx.h"#include <iostream>#include <string>#include <vector>using namespace std; typedef vector<int> T;typedef vec...
算法导论 练习题 15.4-5
根据自己思路写的最长公共子序列,稍微修改一下就行了 static int getlastPos(char *s,char c,int pos) { int len=strlen(s),i; for(i=pos-1;i>=0;i--) { if...
算法导论第15章练习题 15.4-5
15.4-5设计一个O(n²)时间的算法,求一个n个数的序列的最长单调递增子序列。 第一种:对序列进行排序,排序之后得到序列b与原来的序列a,求最长公共子串。(排序之前先将原来序列中的重复元素删掉(保证公共子串递增)b中无重复元素,a保持原来不变) 第二种: def longestIncreas...
算法导论第15章练习题 15.4-4
说明如何仅用表c中的2·min(m,n)项以及O(1)的额外空间来计算一个LCS的长度。然后说明如何用min(m,n)项以及O(1)的额外空间来做到这一点。 1、两行数组,第一个存储上一行的c[i,j],第二个存储当前行的c[i,j]。最开始第一行数组初始化为0. c表最左侧一列 全为0,不需要用...
算法导论 练习题 6.1-7
根据完全二叉树性质,n0=n2+1, 所以n=n0+n1+n2=2n0+n1-1 因为在完全二叉树中n1=0或者1,所以n=2n0-1或n=2n0,所以n0=(n+1)/2或n0=n/2 现在计算一下除了叶子节点之外的节点,数量为(n-1)/2或者n/2,即n/2向下取整 这样就得到需要证明的结论了...
算法导论 练习题 17.2-2
设每个2的幂代价为2i+(2i-2i-1),其余为0,其中i>=1 and i<=lgn 则总代价为∑2i+(2i-2i-1)=O(n)
算法导论 练习题 4.2-3
在行列末尾添加0,直到规模达到最接近的2的n次方。 证明等看完后面再做。
算法导论 练习题 4.3-9
令m=lgn T(2m)=3T(2m)+m 令S(m)=T(2m) 则S(m)=3S(m/2)+m 主方法还没看 解不出这个递归式。 ...
推荐引擎算法学习导论-(协同过滤、聚类、分类、模糊和精确k-means算法等)
推荐引擎算法学习导论:协同过滤、聚类、分类 作者:July。出处:结构之法算法之道引言 昨日看到几个关键词:语义分析,协同过滤,智能推荐,想着想着便兴奋了。于是昨天下午开始到今天凌晨3点,便研究了一下推荐引擎,做了初步了解。日后,自会慢慢深入仔细研究(...
算法导论 练习题 4.2-6
1、将A=kn*n和B=n*kn分别拆成k个n*n矩阵:A11,A21......AK1和B11,B12......B1K A和B相乘得k*k的矩阵,(A11*B11,A11*B12......A11*B1K......AK1*B11,AK1*B12...AK1*B1K) 对...
模式识别导论大作业(k均值算法,感知器算法,fisher算法,贝叶斯决策,特征提取)
模式识别导论大作业 一、 K均值聚类 1. 功能描述: 利用K-均值算法将150个模式样本分成3类别。分别计算最后算法所用的迭代次数,最终聚类中心以及每个类别中对应模式样本的序号。 2. 带注释的源代码 #include "stdio.h" #include "...
算法导论课后习题解析 第三章
3.1-1分情况讨论当$f(n) \ge g(n)$时,$max(f(n), g(n))=f(n)$,存在$c_1=\frac 12,c_2=1,n_0>0$使得$$0 < c_1(f(n)+g(n)) \le f(n) \le c_2(f(n)+g(n)) 对于所有n \ge n_0$...
《算法导论》课后题--4--第三章
3.1-1 证明: f(n),g(n)均为渐进非负函数,所以f(n)+g(n)也是渐进非负函数;故存在正常量n0,当n>=n0时,有:;进一步有:;又因为,将两式相加除以2得:,所以由课本定义可得:。 ----------------------------------------------...
算法导论课后习题解析 第四章 上
4.1-1返回只包含绝对值最小的元素的子数组。 4.1-2 Maximun-Subarray(A)max = -infinityfor i = 1 to A.lengthsum = 0for j = i to A.lengthsum = sum + A[i]if sum > maxmax...
算法导论3.1练习题
3.1-1: 假设0⩽c1(f(n)+g(n))⩽max(f(n),g(n))⩽c2(f(n)+g(n)) ∴0⩽c1(x+y)⩽x+y+|x−y|2⩽c2(x+y) ∵0⩽|x−y|⩽x+y ∴0⩽12(x+y)⩽x+y+|x−y|2⩽x+...
算法导论学习-heapsort
heap的定义:如果数组a[1,....n]满足:a[i]>a[2*i] && a[i]>a[2*i+1],1<=i<=n/2,那么就是一个heap,而且是max-heapheap有两种,max-heap 和 min-heap,其中min-heap的性质与上面...