实验一 算法优化技巧与时间复杂度

【实验目的】
1.学习算法中常见的优化技巧
2.分析算法的时间复杂度
3.在设计应用中能从时间复杂度的角度优化算法设计
【实验内容】

#include<stdio.h> int main(){int a[5][10];//二维数组存放科目和学号int n,m;//n为科目数量，m为学生人数int b[10]={0};int i,j;char k;printf("请输入科目数量和学生人数：\n");scanf("%d%d%*c",&n,&m);for(i=0;i<n;i++){j=0;printf("请依次输入第%d课及格学生学号\n",i+1);do{scanf("%d",&a[i][j]);b[a[i][j]]++;j++;k=getchar();}while(k!='\n');}printf("全部及格学生学号为：");for(i=0;i<m;i++){if(b[i]==3)printf("%d ",i);}return 0; }

（1）用二维指针的存储方式可以提高算法的效率
（2）算法的时间复杂度为O（n）

对于位置长度的存储结构，可以用do—while语句

do{

scanf("%d",&a[i][j]);

j++;

k=getchar();

}while(k!=’\n’);

int main(){int a[100];int i,j,n=1;char k;printf("依次输入要排序的数组元素:\n");do{scanf("%d",&a[n]);n++;k=getchar();}while(k!='\n');for(i=2;i<=n;i++){if(a[i]<a[i-1]){//插入第i个结点a[0]=a[i];//复制为哨兵for(j=i-1;a[0]<a[j];j--){a[j+1]=a[j];//记录后移}a[j+1]=a[0];//插入到正确位置}}printf("排序后的数组元素为：\n") ;for(i=2;i<=n;i++){printf("%d ",a[i]);}return 0; }

（1）最好情况下时间复杂度为O（n）
（2）最坏情况下时间复杂度为O（n²）
（2）算法平均情况下时间复杂度为O（n+n²/2）