adaboost算法及其应用总结.doc

adaboost算法及其应用总结
2

———————————————————————————————— 作者：
———————————————————————————————— 日期：

个人收集 仅供参考学习 勿做商业用途
东 北 大 学
研 究 生 考 试 试 卷
评分
考试科目： 数学算法
课程编号：
阅 卷 人：
考试日期：
学生姓名： 郑罗丹
学生学号： 1300203
注 意 事 项
1．考 前 研 究 生 将 上 述 项 目 填 写 清 楚
2．字 迹 要 清 楚，保 持 卷 面 清 洁
3．交 卷 时 请 将 本 试 卷 和 题 签 一 起 上 交
东北大学研究生院
3

个人收集 仅供参考学习 勿做商业用途
算法总结
一、冒泡排序
算法根本思想：
在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进展比拟和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比拟后发现它们的排序与排序要求相反时，就将它们互换。
算法流程图：
开场
开场
开场
算法复杂度：冒泡排序是稳定的，算法时间复杂度为O(n^2)。
算法的应用：冒泡排序主要应用于教学。
二、合并排序
算法根本思想：
4

个人收集 仅供参考学习 勿做商业用途
合并排序是建立在归并操作上的一种有效的排序算法。合并排序法是将两个〔或两个以上〕有序表合并成一个新的有序表，即把待排序序列分为假设干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。假设将两个有序表合并成一个有序表，称为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)
算法的应用：
四、堆排序
算法的根本思想：
堆排序就是利用堆〔假设利用大顶堆〕进展排序的方法。它的根本思想是，将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根结点。将它移走〔其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值〕，然后将剩余的