算法效率分析..docVIP

《数据结构与算法》实验报告 实验序号：1　　　　　　　　　　 实验项目名称：算法效率分析 学　　号 ****** 姓　　名 ******* 专业、班 ************ 实验地点 ******* 指导教师 ******** 实验时间 ********* 一、实验目的及要求 1.掌握数据结构的形式定义； 2.了解集合、线性表、树和图； 3.理解算法效率分析的基本方法，并分析他们的时间复杂度。 二、实验设备（环境）及要求 微型计算机； windows 操作系统； 计算机软件开发环境（VS2008 \Java开发集成环境\VC6.0）。 三、实验内容与步骤 1.分析下面各程序段的时间复杂度 for (i=0;in;i++) for (j=0;jm;j++) A[i][j]; （2） s=0; for (i=0;in;i++) for (j=0;jn;j++) s+=B[i][j]; sum=s; （3） T=A； A=B； B=T； （4） s1(int n) { int p=1,s=0; for (i=1;i=n;i++) { p*=i;s+=p; } return(s); } （5） x=0; y=0; for (k=1;k=n;k++) x++; for (i=1;i=n;i++) for (j=1;j=n;j++) y++; 2． 根据二元组关系，画出对应逻辑图形的草图，指出它们属于何种数据结构。 (1) A=（D，R），其中： D={a，b，c，d，e}， R={ } (2) B=（D，R），其中： D={a，b，c，d，e，f}， R={a,b，b,c，c,d，d,e，e,f} （尖括号表示结点之间关系是有向的） (3) F=（D，R），其中： D={50，25，64，57，82，36，75，55}， R={50,25,50,64,25,36,64,57,64,82,57,55,57,75} (4) C=（D，R），其中： D={1，2，3，4，5，6}， R={1,2,2,3,2,4,3,4,3,5,3,6,4,5,4,6} （尖括号表示结点之间关系是有向的） 3．试写一个算法，自大到小依次输出顺序读入的三个整数X,Y,Z的值。并请考虑算法在最好情况下和最坏情况下数据移动的次数。 4．试仿照三元组的抽象数据类型分别写出抽象数据类型有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 四、实验结果与数据处理（实验记录） 1.(1)o(n2) (2) o(n2) (3) o(1) (3) o(n) (4) o(n2) 2. (1) . . . . . a b c d e (2) (3) (4) 3. //试写一个算法，自大到小依次输出顺序读入的三个整数X,Y,Z的值。并请考虑算法在最好情况下和最坏情况下数据移动的次数。 static void Main(string[] args) { int[] a = new int[3]; int temp; for (int i = 0; i 3; i++) { a[i] = Convert.ToInt32(Console.ReadLine()); } for (int j = 0; j 2; j++) { for (int l = 2; l j; l--) { if (a[l] a[l - 1]) { temp = a[l]; a[l] = a[l - 1]; a[l - 1] = temp; } } } for (int k = 0; k 3; k++)