第一章作业与练习.docVIP

第 1 章作业与练习 姓名：李明远 学号：1130310126 八. 算法设计（要求：算法用伪代码和 C/C++/Java 描述，并分析最坏情况下的时间复杂度） 对一个整型数组 A[n]设计一个排序算法。 ① 伪代码实现： void DataSort(array a[],int n) { int i,j,temp; for(i←0; in-1; i++) { for(j=i+1; jn; j++) { if(a[i]a[j]) swap (a[i],a[j]) } } } ② c代码实现： void DataSort(int a[],int n) { int i,j,temp; for(i=0; in-1; i++) { for(j=i+1; jn; j++) { if(a[i]a[j]) { temp=a[j]; a[j]=a[i]; a[i]=temp; } } } } ③ 最坏情况下时间复杂度分析： ⑴ 基本语句： if(a[i]a[j])。 ⑵ 问题规模： n。 ⑶ 每执行temp=a[j]，a[j]=a[i]，a[i]=temp时，耗时为O(1),循环次数为 n-j-1,外层循环执行n-1次，所以总共耗时为O(1)*(n-j-1)*(n-1),所以最坏情况下时间复杂度为O(n^2)。 找出整型数组 A[n]中元素的最大值和次最大值。 ① 伪代码实现： void SortTwo(array a[],int n) { int i,j,temp； for(i←0; i2; i++) { for(j=i+1; jn; j++) { if(a[j]a[i]) swap(a[i]，a[j])； } } } ② c代码实现： void SortTwo(int a[],int n) { int i,j,temp; for(i=0; i2; i++) { for(j=i+1; jn; j++) { if(a[j]a[i]) { temp=a[j]; a[j]=a[i]; a[i]=temp; } } } } ③ 最坏情况下时间复杂度分析： ⑴ 基本语句： if(a[j]a[i])。 ⑵ 问题规模： n。 ⑶ 每执行temp=a[j]，a[j]=a[i]，a[i]=temp时，耗时为O(1),循环次数为 n-j-1,外层循环执行2次，所以总共耗时为2*n*O(1)，所以时间复杂度为O(n)。 3． A 是一个有 n 个不同元素的实数数组，写出确定给定实数 K 是否在 A 中的算法，分析时间复杂性（要求：问题规模、基本语句，O 记号），并在极器验证你的复杂度。 ① 伪代码实现： int Found(float a[],int n,float s) { int i； for(i←0;in;i++) { if(fabs(a[i]-s)=1e-5) 函数返回值为1； } 否则函数返回值为0； } ② c代码实现： int Found(float a[],int n,float s) { int i; for(i=0;in;i++) { if(fabs(a[i]-s)=1e-5) return 1; } return 0; } ③ 最坏情况下时间复杂度分析： ⑴ 基本语句： if(fabs(a[i]-s)=1e-5) ⑵ 问题规模： n。 ⑶ 每执行if(fabs(a[i]-s)=1e-5)时，耗时为O(1),外层循环次数为n次， 所以总共耗时为n*O(1)，所以时间复杂度为O(n)。