博文
转算法复杂度的分析方法及其运用(2007-12-19 16:17:00)
摘要：算法复杂度是在《数据结构》这门课程的第一章里出现的，因为它稍微涉及到一些数学问题，所以很多同学感觉很难，加上这个概念也不是那么具体，更让许多同学复习起来无从下手，下面我们就这个问题给各位考生进行分析。
首先了解一下几个概念。一个是时 间复杂度，一个是渐近时 间复杂度。前者是某个算法的时 间耗费，它是该算法所求解问题规模n的函数，而后者是指当问题规模趋向无穷大时，该算法时 间复杂度的数量级。
当我们评价一个算法的时 间性能时，主要标准就是算法的渐近时 间复杂度，因此，在算法分析时，往往对两者不予区分，经常是将渐近时 间复杂度T(n)=O(f(n))简称为时 间复杂度，其中的f(n)一般是算法中频度最大的语句频度。
此外，算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。但是我们总是考虑在最坏的情况下的时 间复杂度。以保证算法的运行时 间不会比它更长。
常见的时 间复杂度，按数量级递增排列依次为：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、k次方阶O(n^k)、指数阶O(2^n)。
下面我们通过例子加以说明，让大家碰到问题时知道如何去解决。
1、设三个函数f,g,h分别为 f(n)=100n^3 n^2 1000 , g(n)=25n^3 5000n^2 , h(n)=n^1.5 5000nlgn
请判断下列关系是否成立：
（1） f(n)=O(g(n))
（2） g(n)=O(f(n))
（3） h(n)=O(n^1.5)
（4） h(n)=O(nlgn)
这里我们复习一下渐近时 间复杂度的表示法T(n)=O(f(n))，这里的"O"是数学符号，它的严格定义是"若T(n)和f(n)是定义在正整数集合上的两个函数，则T(n)=O(f(n))表示存在正的常数C和n0 ,使得当n≥n0时都满足0≤T(n)≤C?f(n)。"用容易理解的话说就是这两个函数当整型自变量n趋向于无穷大时，两者的比值是一个不等于0的常数。这么一来，就好计算了吧。
◆ (1)成立。题中由于两个函数的最高次项都是n^3,因此当n→∞时，两个函数的比值是一个常数，所以这个关系式是成立的。
◆ （2）成立。与上同理。<......
转用Visual C++实现排序算法大全(2007-12-19 15:58:00)
摘要： 1.引言
2005年10月25～26日，包括笔者在内的十多位成员组队参加了武汉原动力的野外拓展（Outward Bound）。在攀岩悬崖之前，教官组织了这样的一个游戏项目：
教官将团队里的所有成员分开，然后用布条蒙上大家的眼睛，接着给每人一个3位或4位的数字。他要求成员们蒙着眼睛集合，在不说话也看不到彼此的情况下，在限定的时间内，按所分得数字的大小顺序排成一条线。
要成功地完成这个游戏的确有相当的难度，成员们唯一可以借助的分辨彼此大小的手段可能是摸手指、拍肩膀或跺脚等，而要在限定的时间内分别出所有的大小并排成一条线却依赖一个好的排序算法。 最后我们团队失败了，我们这群都有一定数据结构和算法学习背景的所谓IT人败在了这个游戏的面前。最后，教官对我们进行了一番“团队合作精神如此重要”之类的教育云云。
本文对排序算法的全面论述将从这个游戏说开去，并用Visual C++ 6.0编写一个示例工程以动画演示这个游戏中的成员以各种算法实现成功排序的过程。排序算法是数据结构学科的经典内容，也是计算机科学中最重要的研究问题之一。由于它的应用广泛和固有的理论上的重要性，2000年它被列为对科学和工程计算的研究与实践影响最大的10大问题之一。对于排序的研究既有理论上的重要意义，又有实际应用价值。它在计算机图形、计算机辅助设计、机器人、模式识别、及统计学等领域具有广泛应用。 常见的排序算法有起泡排序、直接插入排序、简单选择排序、快速排序、堆排序等。在演示完各种排序算法的动态过程后，本文将给出面对特定问题时选用合适排序算法的原则。
2.演示工程
单击此处下载演示工程。
以Visual C++编写一个基于对话框的程序，我们假设待排序的队员的总数为10，排序的整个过程为（每个步骤对应一个菜单）：
（1）队员分散：模拟教官将队员分散开来的过程
对应的菜单为：IDM_Disperse_Member
菜单标题为：队员分散 （2）分配数字：模拟教官给每个队员一个3位或4位的数字的过程
对应的菜单为：IDM_CREAT_NUMBER
菜单标题为：产生数字
......
转快速排序算法(2007-12-19 15:35:00)
摘要：
快速排序算法
佚名
快速排序是对冒泡排序的一种改进。它的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
假设要排序的数组是A[1]……A[N]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一躺快速排序的算法是：
1）、设置两个变量I、J，排序开始的时候I：=1，J：=N；
2）以第一个数组元素作为关键数据，赋值给X，即X：=A[1]；
3）、从J开始向前搜索，即由后开始向前搜索（J：=J-1），找到第一个小于X的值，两者交换；
4）、从I开始向后搜索，即由前开始向后搜索（I：=I+1），找到第一个大于X的值，两者交换；
5）、重复第3、4步，直到I=J；
例如：待排序的数组A的值分别是：（初始关键数据X：=49）
A[1] A[2] A[3] A[4] A[5] A[6] A[7]：
49 38 65 &nbs......
转排序总结(2007-12-19 14:52:00)
摘要：
一、排序的概念
所谓排序，就是要让所有元素按递增或递减的顺序排列。
二、排序的分类
内部排序：只在主存中完成的排序(由于主存有限，所以内部排序的元素是有上限的)。
外部排序：利用磁盘等外存进行排序。
三、排序的稳定性
在待排序的元素中，存在多个相同的元素，经过排序后，这些元素的相对位置不变，该排序法就为稳定排序，否则为不稳定排序。
四、内部排序法
-----------------------------------------------------------
1.插入排序
算法思想
假设待排序的元素存放在数组A[N]中。初始时，A[0]自成1个有序区，无序区为A[1]~A[N-1]。从i=1起直至i=N-1为止，依次将A[i]插入当前的有序区A[0]~A[i-1]中。排序结束后为含N个元素的有序区。算法的平均时间复杂度为O(N^2)。
程序实现
void
InsertionSort( ElementType A[], int N )
{
int j, P;
ElementTyep Tmp;
for( P = 1; P < N; P++ );
{
Tmp = A[ P ];
for( j = p; j > 0 && A[ j - 1 ] > Tmp; j-- )
A[ j ] = A[ j - 1 ];
A[ j ] = Tmp;
}
}--------------------------------------------------------
2.希尔排序
算法思想
假设有N个待排序的元素，先取一个小于N的整数d1作为第一个增量，把所有距离为d......