NOIP初赛复习13排序与算法复杂度

NOIPNOIP 初赛复习初赛复习 1313 排序与算法复杂度排序与算法复杂度 排序 排序（Sorting）是计算机程序设计中的一种重要操作，其功能是对一个数据元 素集合或序列重新排列成一个按数据元素某个项值有序的序列。 简单排序算法 简单排序算法包括冒泡排序、插入排序、选择排序。这三种算法容易理解、编写 方便，适用于数据规模较小的情形。 冒泡排序 基本思想：基本思想：两两比较待排序记录的关键字， 发现两个记录的次序相反时即进行交 换，直到没有反序的记录为止。 排序方法：排序方法：依次比较相邻的两个数，将大数放在前面，小数放在后面。 首先比较第 1 个和第 2 个数，将大数放前，小数放后。然后比较第2 个数和第 3 个数，将大数放前，小数放后，如此继续，直至比较最后两个数，将大数放前， 小数放后，此时第一趟结束，在最后的数必是所有数中的最小数。 重复以上过程，仍从第一对数开始比较（因为可能由于第 2 个数和第 3 个数的 交换，使得第 1 个数不再大于第 2 个数），将大数放前，小数放后，一直比较 到最小数前的一对相邻数，将大数放前，小数放后，第二趟结束，在倒数第二个 数中得到一个新的最小数。 如此下去，直至最终完成排序。 效率分析效率分析 空间效率：仅用了一个辅助交换单元。 时间效率：总共要进行 n-1 趟冒泡，对 n 个记录的表进行一趟冒泡需要 n-1 次数值大小比较。 移动次数：移动次数：最好情况下，待排序列已有序，不需移动。 直接插入排序 基本思想：基本思想：依次将每个记录插入到一个有序中去。就是说，第 i 遍整理时， A1,A2,.,Ai-1 已经是排好序的子序列； 取出第 i 个元素 Ai， 在已排好序的子序列 为 Ai找到一个合适的位置，并将它插到该位置上。易知上述排序当 i=1 时实际 上为空操作，故可直接从 i=2 开始。 排序方法：排序方法： 每步将一个待排序的记录按其关键字的大小插到前面已经排序的序列 中的适当位置，直到全部记录插入完毕为止。 效率分析效率分析 空间效率：仅用了一个辅助单元。 时间效率：向有序表中逐个插入记录的操作，进行了 n-1 趟，每趟操作分为比 较关键码和移动记录， 而比较的次数和移动记录的次数取决于待排序列按关键码 的初始排列。 对于 NOIP 提高组而言，这些算法时间复杂度过高，很难应付较大的数据规模。建议尽量 不要采用简单排序算法，除非你十分确信数据规模在可承受范围之内。 快速排序 基本思想：基本思想：基于分治思想。（以从小到大排序为例）取一个数作为标记元素，将 比它大的数放在它右侧，比它小的数放在它左侧，再通过递归的方法，将左侧的 数用以上的方法排好，右侧的数也用以上的方法排好即可。 在数据规模很大时，平均情况下快排比冒泡快很多。在处理NOIP 提高组含排序的问题时， 一般要选择快速排序或堆排序。 排序方法：排序方法：运用分治思想，因而要用函数的递归调用来实现。 快速排序实现方法的最差情形是排列整齐的情况，这时它的运行效率会很低。为 了解决排列整齐的情形，我们可以使用随机快速排序法，即随机选取一个数作为 标记元素（实现时，将其与第一个数交换即可）。 算法时空复杂度 为了描述一个算法的优劣，我们引入算法时间复杂度和空间复杂度的概念。 时间复杂度：时间复杂度：一个算法主要运算的次数，用 O( )表示。 通常表示时间复杂度 时，我们只保留影响最大的项，并忽略该项的系数。 例如主要运算为赋值的算法，赋值做了 3n^3+n^2+8 次，则认为它的复杂度 为 O(n^3)；若主要运算为比较，比较做了 4*2^n+2*n^4+700 次，由于数 据很大时， 指数级增长的 2^n 影响最大， 我们认为它的时间复杂度为 O(2^n)。 常见的时间复杂度：常见的时间复杂度： O(n) ——贪心算法多数情况下为此时间复杂度 O(nlbn)——有时带有分治思想的算法的时间复杂度 (注 lbn 表示以 2 为底的 n 的对数) O(n^2) ——有时动态规划的时间复杂度 O(n^3) ——有时动态规划的时间复杂度O(2^n) ——有时搜索算法的时间复杂度 O(n!) ——有时搜索算法的时间复杂度 O(m*n)——有时时间复杂度中含有两个或多个字母，比如遍历一个m*n 的矩阵，时间 复杂度为 O(m*n) 要注意的是， 时间复杂度相同的两个算法，它的实际执行时间可能会有数倍的差 距，因而实现时要特别注意细节处的优化。 NOIP 提高组执行时限常常为 1s。一般认为，将数据规模代入到时间复杂度，若所得值小 于或接近于 1000000，就是绝对安全的、不超时的。 例如：O(n^2)的动态规划算法，可承受的数据规模是 n≤1000；O(2^n)的搜索算法，可 承受的数据规模是 n≤20；O(n!)的搜索算法，可承受的数据规模是n≤9。实际上，以现在 的 CPU 运行速度，5000000 也应该不成问题。 空间复杂度：空间复杂度：一个算法消耗储存空间(内存)的大小，用 O( )表示。 空间复杂度 的表示规则与时间复杂度类似。 在实际应用时， 空间的占用是需要特别注意的问题。太大的数组经常是开不出来 的，即使开出来了，遍历的时间消耗也是惊人的。 下面我们简单地分析一下简单排序算法、快速排序、堆排序的时空复杂度。这三 种算法都是基于比较的排序算法，以比较次数作为主要运算。 时间上，简单排序算法最差时需做 n^2 次比较，平均情况下时间复杂度通常被 认为是 O(n^2)；快速排序最差时需做 n^2 次比较，可以证明平均情况下需 做 nlbn 次比较，时间复杂度是 O(nlbn)；堆排序时间复杂度是 O(nlbn)。 空间上， 三者都不需要额外开辟暂存数组，快排递归调用时需要使用稍多一些的 储存空间。综合来看，快速排序、堆排序优于简单排序算法。另外，可以证明基 于比较的排序算法时间复杂度下界为 O(nlbn)。 时空的简单优化方法 时间上的优化在于少做运算、做耗时短的运算等。时间上的优化在于少做运算、做耗时短的运算等。有几个规律需要注意： 1、整型运算耗时远低于实型运算耗时。 2、+、-运算非常快(减法是将减数取补码后与被减数相加，其中位运算更快一 些，但是减法也比加法稍慢些。) 3、 *运算比加法慢得多/运算比乘法慢得多比较运算慢于四则运算赋值运算慢于 比较运算(因为要写内存) 这些规律我们可以从宏观上把握。 事实上，究竟做了几步运算、几次赋值、变量在内存还是缓存等多数由编译器、 系统决定。 但是，少做运算（尤其在循环体、递归体中）一定能很大程度节省 时间。 下面来举一个例子： 计算组合数 C(m,n)——n 件物品取出 m 件的组合数。 C(m,n)可用公式 直接计算。C(m,n)=n!/((n-m)!m!)， C(m,n)=n(n-1)(n-2).(n-m+1)/(n-m)!。显然，有时所作的乘法少很多， 会快一些。 可是这样算真的最快吗？另一条思路是 C(m,n)=C(m,n-1)+C(m-1,n-1)， 递推下去， 直到可利用 C(1,k)=k=C(k-1,k)为止。 这种只用加法的运算会快些， 尽管加法多一些。 空间上的优化主要在于减小数组大小、空间上的优化主要在于减