今天学习了算法导论上的归并排序算法,并且完成了在纸上写出伪代码,以前就学过归并但是理解的不够透彻,以前还一直困惑:为什么明明归并排序比快排的时间复杂度更稳定,为什么库函数不用归并而用快排,现在知道原因了,因为归并排序必须开额外的空间,而且空间开销还比较大,下面介绍算法:首先,归并排序用到了分治的思想,把大数据分成若干个小数据,然后再分别对小数据进行处理,最后把小数据合并成大数据。其次,归并排序用到...
本节课介绍了一种全新的数据结构——跳跃表跳跃表是一种简单又有趣的动态搜索数据结构,其主要优点在于其易于实现,而且很好的保证了其具有高效的性能,即2*O(lgn)的搜索性能在此之前我想首先谈谈链表,链表的优点在于其插入和删除只需要常数项的时间(加上查找该元素需要额外的O(n)时间),但是其查找效率只有O(n),这里顺带补充一下链表类的问题,以下先给出两个BAT公司面试时热衷于考的两个链表经典问题:1.如何快速查找单...
许久,你要我写的东西对非技术类没少依赖于博客。来自0学习技术的开始。你会遇到很多类似的问题,我把他们失望。它会给人帮。但是,非技术性的东西,他还写信给自己看的,在不存在的“我想小”转换成“我想为大”之前(看了刘未鹏的博客后的感触),我不须要别人的理解和同情。再者,即使面对面交流,也不能保证使一个人全然理解还有一个人。更何况活的思考变成死的文字。然而今天。我仅仅是想把憋在心里的话写出来。人的层次并不同样...
没办法就是这么没原则,又开了个坑。每天看点书,不管什么书。1. 需求: 输入:n个数的一个序列(a1, a2, a3……an) 输出: 输出序列的一个排列(a1‘, a2‘, a3‘ ……an‘),满足a1‘ <= a2‘ <= a3‘ ……<= an‘2. 图示:3. 伪代码 INSERTION-SORT(A)for j=2 to A.lengthkey = A[j]i = j-1//把A[j]插入到有序数组 A[1...j-1].while i > 0 and A[i] > keyA[i+1] = A[i]i = i -1A[i + 1] = key 4. 理解 算法导论不愧是...
计数排序是一种能够达到运行时间能够线性时间θ(n)的排序算法。在排序算法里算是最快的算法之一,当然,他有很强烈的前提。下面开始介绍一下技术排序(Counting Sort)。算法思想计数排序假设n个输入元素中的每一个都是介于0到k之间的整数,此处k为某个整数。这样可以用一个数组C[0..k]来记录待排序数组里元素的数量。当k=O(n)时,计数排序的运行时间为θ(n).注:关于C[0..k],用键值对描述的话,待排序元素是键,相同元素的个数是...
比较排序:各元素的次序依赖于它们之间的比较{插入排序O(n**2) 归并排序O(nlgn) 堆排序O(nlgn)快速排序O(n**2)平均O(nlgn)}本章主要介绍几个线性时间排序:(运算排序非比较排序)计数排序O(k+n)基数排序O()第一节:用决策树分析比较排序的下界决策树:倒数第二层满,第一层可能满的二叉树,它用来表示所有元素的比较操作{于此来分析下界},忽略控制,移动操作1:2 #A[1]和A[2]比 <= 走左边 >走右边<3,1,2> 最后的结果 下标对应排序...
5.1-2 生成Random(a,b) 运行b-a次Random(0,1),累加和,最后再加a5.1-3 等概率生成0和1 Biased-Random 以概率p输出1,以概率1-p输出0, 则1-Biased-Random 以概率p输出0,以概率1-p输出1 则调用Biased-Random后接着调用1-Biased-Random,出现的概率为 调用结果 00 01 10 11 出现概率 (1-p)*p (1-p)*(1-p) p*p
p*(1-p)则1出现的期望E[1] = (1-p)*(1-p) + p*p + ...
第一章 算法在计算中的作用 1.1 算法算法是任何良定义的计算过程,该过程取某个值或值的集合作为输入并产生某个值或者值的集合作为输出。对每个输入实例,算法都以正确的输出停机,则称该算法是正确的。算法的运行时间:$\log{n} < \sqrt{n} < n < n\log{n} < n^2 < n^3 < 2^n < n!$原文:http://www.cnblogs.com/lainey/p/7904233.html
#pragma once
#include<iostream>
using namespace std;/*返回节点i的父结点*/
int Parent(int i)
{if (i <= 0)return -1;elsereturn (i - 1) / 2;
}
/*返回节点i的左孩子*/
int Left(int i)
{return 2 * i + 1;
}/*返回结点i的右孩子*/
int Right(int i)
{return 2 * i+2;
}
/*交换两个数*/
template<class T>
void Swamp(T &a, T &b)
{T temp;temp = a;a = b;b = temp;
}
/*维护最大堆的性质
inputData为输入的数组
rootNode为根...
#include<iostream>
using namespace std;
int bottom_up_cut_rod(int p[],int n,int &pos)
{int *r=new int[n+1];int *s=new int[n+1];for(int i=0;i<=n;++i)s[i]=0;for(int i=0;i<=n;++i)r[i]=0;for(int j=1;j<=n;++j){int q=-1;for(int i=1;i<=j;++i){//q=q>p[i]+r[j-i]?q:p[i]+r[j-i];if(q<p[i]+r[j-i]){q=p[i]+r[j-i];s[j]=i;}}r[j]=q;}pos=s[n];return r[n];
}
int main()
{const int size=10 ;int p[11]={0,1,5,8,9,10,17,1...
动态规划注:该篇为本人原创,转载请注明出处:http://blog.csdn.net/chudongfang2015/article/details/51590817 ——开心 -.-个人对动态规划的理解:1.动态规划是一个付出额外空间来节省时间,就是所谓的空间换时间。2.动态规划储存每个状态的最优解。3.动态规划是用来把子问题的结果储存下来,再次用到的时候就不必再进行重复计算。算法导论对动态规划的解释:动态规划和分治方法相似,都是通过组合子问题的解来求解原问题,分治方...
一、电子围栏定位算法:还是决定不做定位算法了,原因有下:1.文献[1]中利用线性算法解决了TDOA问题(四个观测点以上),文献[2]中将AOA算法的形式也纳入进来。多个直线的交点就是待测点的位置。如果考虑单点是否在围栏内部,之前做的假设是,定位单点的算法复杂度高,但这两篇文献中说明的是:理论上是线性的,很简单。根据四个及以上观测量可将问题变成线性问题求解的后续扩展思路是,1结合新的应用场景和实际数据,得到算法应用...
1 INSERTION - SORT (A)2 for j= 2 to A.length
3 key = A[j]
4 // Insert A[j] into the sorted sequence A[1..j-1]
5 i = j - 16while i>0 and A[i]>key
7 A[i+1]=A[i]
8 i = i - 1
9 A[i+1] = key首先,算法导论书上的类代码如上述.首先要理解的是,算法导论上的类代码并不是从 0 开始 ,而是从 1 开始的, 因此不要奇怪为何 第一行是 从 j = 2开始循环,当然<<算法导论>>上也介绍了 循环不变式 ...
目录 1、计数排序介绍 2、流程图 3、代码实现 4、性能分析 5、参考资料内容 1、计数排序介绍 什么是计数排序? 计数排序是一种特殊的排序算...
讨论内容不说明,仅提供相应的程序。2.1:归并插入排序θ(nlgn)void mergeInsertionSort(int a[], int l, int r, int k)
{int m;if(r-l+1 > k){m = (l + r) / 2;mergeInsertionSort(a, l, m, k);mergeInsertionSort(a, m+1, r, k);merge(a, l, m, r);}elseif(l < r)insertSort(a, l, r);
}void insertSort(int a[], int l, int r)
{int i, j, key;j = l;for(i=l+1; i<=r; i++)if(a[i] < a[j]) j = i;if(j > l){key = a[j];a[j] = a[...