adaboost算法及其应用总结.doc

东北大学
研究生考试试卷
评分
考试科目: 数学算法
课程编号:
阅卷人:
考试日期:
学生姓名: 郑罗丹
学生学号: 1300203
注意事项

,保持卷面清洁

东北大学研究生院
算法总结
一、冒泡排序
算法基本思想:
在要排序的一组数中,对当前还未排好序的范围内的全部数,自上而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒。即:每当两相邻的数比较后发现它们的排序与排序要求相反时,就将它们互换。
算法流程图:
开始
开始
开始
算法复杂度:冒泡排序是稳定的,算法时间复杂度为O(n^2)。
算法的应用:冒泡排序主要应用于教学。
二、合并排序
算法基本思想:
合并排序是建立在归并操作上的一种有效的排序算法。合并排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。
算法的基本流程:
1. 分解:将n个数的序列分解为2个包含n/2个数的子序列;
2. 解决:使用合并排序算法递归地对这2个子序列进行排序;
3. 合并:合并2个已经排序的子序列以得到最终的排序结果。
算法复杂度:时间复杂度为O(NlogN),空间复杂度
算法的应用:
三、快速排序
算法基本思想:
通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
算法的基本流程:
1. 设置两个变量i、j,排序开始的时候:i=0,j=N-1;
2. 以第一个数组元素作为关键数据,赋值给key,即key=A[0];
3. 从j开始向前搜索,即由后开始向前搜索(j--),找到第一个小于key的值A[j],将A[j]赋给A[i];
4. 从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于key的A[i],将A[i]赋给A[j];
5. 重复第3、4步,直到i=j。
算法复杂度:
最好的情况下空间复杂度 O(log n)
最坏的情况下空间复杂度 O(n)
时间复杂度 O(n*log n)
算法的应用:
四、堆排序
算法的基本思想:
堆排序就是利用堆(假设利用大顶堆)进行排序的方法。它的基本思想是,将待排序的序列构造成一个大顶堆。此时,整个序列的最大值就是堆顶的根结点。将它移走(其实就是将其与堆数组的末尾元素交换,此时末尾元素就是最大值),然后将剩余的n-1个序列重新构造成一个堆,这样就会得到n个元素中的次小值。如此反,便能得到一个有序序列了复执行。
算法的基本流程:
1. 将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆,此堆为初始的无须区;
2. 将堆顶元素R[1]与最后一个元素R[n]交换,此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R[1,2...n-1]<=R[n];
3. 由于交换后新的堆顶R[1]可能违反堆的性质,因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆,然后再次将R[1]与无序区最后一个元素交换,得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1,无序区只有一个元素为止,则整个排序过程完成。
算法的复杂度:
时间复杂度为:O(n log n)
空间复杂度为:O(1)
算法的应用:
堆排序的主要用途,是在形成和处理优先级队列方面,如果计算要求是类优先级队列(比如,只要返回最大或者最小元素,只有有限的插入要求等), 堆同样是很适合的数据结构。另外,堆排序还广泛应用于计算机领域。
五、折半查找
算法的基本思想:
对于有序表,查找时先取表中间位置的记录关键字和所给关键字进行比较,若相等,则查找成功;如果给定值比该记录关键字大,则在后半部分继续进行折半查找;否则在前半部分进行折半查找,直到查找范围为空而查不到为止。折半查找的过程实际上是先确定待查找元素所在的区域,然后逐步缩小区域,直到查找成功或失败为止。
算法的基本步骤:
:

2. 然后将待查的K值与R[mid].key比较:若相等,则查找成功并返回此位置,否则须确定新的查找区间,继续二分查找。
具体方法如下:
①若R[mid].k