adaboost算法及其应用总结.doc

东 北 大 学 研 究 生 考 试 试 卷 评分 考试科目： 数学算法 课程编号： 阅 卷 人： 考试日期： 学生姓名： 郑罗丹 学生学号： 1300203 注 意 事 项 1．考 前 研 究 生 将 上 述 项 目 填 写 清 楚 2．字 迹 要 清 楚，保 持 卷 面 清 洁 3．交 卷 时 请 将 本 试 卷 和 题 签 一 起 上 交 东北大学研究生院 算法总结 一、冒泡排序 算法基本思想： 在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。 算法流程图： 开始 开始 开始 算法复杂度：冒泡排序是稳定的，算法时间复杂度为O(n^2)。 算法的应用：冒泡排序主要应用于教学。 二、合并排序 算法基本思想： 合并排序是建立在归并操作上的一种有效的排序算法。合并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。 算法的基本流程： 1. 分解：将n个数的序列分解为2个包含n/2个数的子序列； 2. 解决：使用合并排序算法递归地对这2个子序列进行排序； 3. 合并：合并2个已经排序的子序列以得到最终的排序结果。 算法复杂度：时间复杂度为O(NlogN)，空间复杂度 算法的应用： 三、快速排序 算法基本思想： 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以HYPERLINK /view/96473.htm递归进行，以此达到整个数据变成有序序列。 算法的基本流程： 1. 设置两个HYPERLINK /view/296689.htm变量i、j，HYPERLINK /view/58783.htm排序开始的时候：i=0，j=N-1； 2. 以第一个HYPERLINK /view/209670.htm数组元素作为关键数据，赋值给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,R2Rn)构建成大顶堆，此堆为初始的无须区； 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,R2Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，无序区只有一个元素为止，则整个排序过程完成。 算法的复杂度： 时间复杂度为：O(n log n) 空间复杂度为：O(1) 算法的应用： 堆排序的主要用途,是在形成和处理优先级队列方面，如果计算要求是类优先级队列(比如，只要返回最大或者最小元素，只有有限的插入要求等), 堆同样是很适合的数据结构。另外，堆排序还广泛应用于计算机领域。 五、折半查找 算法的基本