程序设计基础 (2).pptVIP

如何选择合适的算法选择指标正确性效率可读性可维护性算法评估：在诸多因素中寻找平衡点高效的算法可读性差，可读性好的算法效率一般不高第30页，共70页，星期日，2025年，2月5日最大公约数问题函数原型intgcd(intx,inty);两种算法实现策略穷举法：逐一尝试所有可能值欧几里德算法步骤1：x除以y，余数为r步骤2：若r为0，则n为所求，算法终止；否则步骤3：将y作为新x，r作为新y，返回第1步第31页，共70页，星期日，2025年，2月5日最大公约数问题穷举法实现intgcd(intx,inty){intg;g=x;while(x%g!=0||y%g!=0)g--;returng;}第32页，共70页，星期日，2025年，2月5日最大公约数问题欧几里德算法实现intgcd(intx,inty){intr;while(1){r=x%y;if(r==0)break;x=y;y=r;}returny;}第33页，共70页，星期日，2025年，2月5日11.5算法分析与算法复杂度算法分析的目的评估算法的执行效率排序算法选择排序归并排序算法复杂度第34页，共70页，星期日，2025年，2月5日选择排序函数原型voidSortIntegerArray(inta[],intn);基本原理依次找最小元，将最小元与数组未排序的第一位互换重复上述步骤第35页，共70页，星期日，2025年，2月5日选择排序原始数组5625375895197330a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]第一趟1925375895567330a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]第二趟1925375895567330a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]第36页，共70页，星期日，2025年，2月5日选择排序#includestdio.hvoidSortIntergeArray(inta[],intn){intlh,rh,i,temp;for(lh=0;lhn;lh++){rh=lh;for(i=lh+1;in;i++){if(a[i]a[rh])rh=i;}temp=a[lh];a[lh]=a[rh];a[rh]=temp;}｝voidmain(){inti,numbers[8]={56,25,37,58,95,19,73,30};SortIntegerArray(numbers,8);for(i=0;i8;i++)printf(“%7d”,numbers[i]);}第37页，共70页，星期日，2025年，2月5日选择排序算法的性能分析程序执行时间T随问题规模n显著增加算法的主要执行时间在于循环循环执行次数(n2+n)/2算法执行时间的估计与测量平方级算法执行时间：T?n2第38页，共70页，星期日，2025年，2月5日算法复杂度算法复杂度的定义算法的执行效率随问题规模的变化趋势算法复杂度的分类时间复杂度：算法执行时间空间复杂度：算法所需存储空间第39页，共70页，星期日，2025年，2月5日大O表达式算法复杂度的度量：大O表达式近似描述算法的本质例：O(n2)表示算法复杂度与问题规模的平方近似成正比原则忽略所有对变化趋势影响较小的项忽略所有常数因子例：算法需要2n+3n2步骤才能完成，时间复杂度为O(2n)第40页，共70页，星期日，2025年，2月5日算法时间复杂度的估计时间复杂度计算total赋值1次i赋值1次；in执行n+1次；i++执行n次循环体内部代码执行n次返回值执行1次总计：3n+4次；时间复杂度：O(n)doubleAverage(doublea[],intn){inti;doubletotal;total=0;for(i=0