算法分析与优化

福建电脑JJIAN COMPUTER算法分析与优化茹小光(长治医学院计算机中心山西长治046000【摘要】:本文介绍了笔者在程序设计过程中针对同一问题的不同算法进行分析,从算法执行的时间和算法运行使用的空间入手,对每种算法进行分析比较,不断改进和优化算法,以求获得算法在运行时间和使用空间上的最优。【关键词】:算法;时间;空间;效率;因子1引言01for(1-2;1<=n;i+)在进行程序设计时,同一问题可以用不同的算法03for(j-2;-;解决,而一个算法的质量优劣将影响到程序运行的效玉f(ij==8)f1ag-1;8s if(flags)率。在存储空间和程序运行时间要求苛刻的情况下07 printf("2d".1);就必须对各种算法进行分析,其目的在于选择合适算Flag法和改进算法。算法分析主要是指分析算法的效率,它主要包含两方面的内容:算法的运行时间和运行使图1前三种算法采用结构用空间。我们可以通过对同一问题的不同算法分析来其中,“口”处可依次用n-1、n/2、sqr(m)分别代替评价这些算法的优劣。形成前面对应算法。2算法的运行时间上述三种算法采用的都是双循环结构,无论是判一个算法执行所耗费的时间,从理论上是不能算断单个数还是判断完所有数,三种算法的运行次数显出来的,必须上机运行测试才能知道。但我们不可能然是不同的,算法一执行次数最多,算法二位列其次,也没有必要对每个算法都上机测试,我们可以通过算算法三执行次数最少。然而如果我们逆向思维,结合法花费的时间与算法中语句的执行次数成正比这种第三种算法思想,以范围内所有整数的可能最简因子关系来判断不同算法执行所耗费的时间的不同。下面作为外循环,内循环采用排除法,排除那些因子倍数我们通过分析一个具体问题的不同算法来说明各种的非素数,最后剩下的便是我们所要的范围内的所有算法的执行时间效率。素数,具体算法如图2所示算法四函数模块。问题描述:求范围[2,n内的所有素数(质数)。01 void prime(unsigned n)眨2《算法一:判断一个整数n是否是素数,可依次进83 unsigned 1, j:行n/2,m3,…,m(m-1)试除,如果都没有除尽,则n是51f(n<2)素数,否则n不是素数。简单说:就是试除到n的前87 arr=(int )malloc(n+1):08 For(1-2: i<-n: 1++)个数。arr[1]=118 for(i-2: i<-sgrt(n): 1++)f(arr[iD)算法二:判断一个整数n是否是素数,可依次进For(j2;=n;+1)行n/2,n/3,,n(m2)试除,如果都没有除尽,则n是素arr[l-o14for(i2;i<-n;1*if(arr[i])数。否则n不是素数。简单说:就是试除到n的二分之printf("2d".1):ee(arr处算法三:判断一个整数n是否是素数,可依次进图2算法四函数模块行n2,n3,, n/sqrt(n)试除,如果都没有除尽,则n是素算法四同算法三比较,算法执行的时间进一步缩数;否则n不是素数。简单说:就是试除到n的开平方短了,但带*L「中国煤化工过程中增加了根处。内存空间的开CNMHG为我们接下来上述三种算法都涉及到如下双循环语句结构:需要改进算法的自的在。下转第119页)114·福建电脑2014年第1期福建电脑JIAN COMPUTER和皮肤还比较僵硬,动物运动的姿势还不够真实,衣画的前景一片光明。服随着人的运动还不能真实反映其效果,气候的变化要实时准确模拟还有很多路要走四;植物的3D动画效参考文献:果更是重点的研究目标,还有图形和图像在动态中融[1]程昌华,建筑动画的发展现状叮],考试周刊,201246,合、情感在建筑物中的表现,以及美学、电影等表现手17-24法都是当前的研究方向吲[2]张志腾.浅析当前建筑漫游动画的优势与发展前景[J]丝绸之路,2009(8),79-80政府提倡加快城镇建设,有政府的支持,建筑动3李希,张行,三维动画在建筑设计中的运用一建筑动画产业作为新媒体环境下的新兴产业,应用越来越广(4}傅建华,李侍琳,孔晖关于天津历史风晚建筑保护机制的泛,前景十分看好;在建筑设计、城乡规划、园林设计探索[C,第二届历史建筑遗产保护与可持续发展国际会议论和自然文化遗产保护等领域都具有强劲的竞争力。随文集。天津:天津大学出版社,2010,34-36着软硬件技术的进步,三维建筑动画设计和制作变得[5](美) eremy Birn译者:吴洪涛,王华,等,图形图像:数字更为容易,用户只要有一台较高配置的个人电脑就绘图中的光照与渲染[M.北京:电子工业出版社,2001可以参与到该行业的竞争,使得更多建筑动画的爱好[6]田美山浅谈建筑动画的表现方法与优势冂、中国电子者和创业者加入到该行业中,这对我国的建筑动画的商务20130343发展和对国内动画整体水平的提升,更具有积极的意MsG, Wang Wo. Effectively Discriminating Fighting Shots义。同时随着力学、数字化、美学、音乐等元素的加入in Action Movies[JJ. Computer Science and Technology.2011, 26(1):187-194加上电影等表现手法应用到建筑的动画中,使得建筑8] LiangXH, Mas, CenLX,et al. Light Space Cascaded Shadow环境中的情感更加表现突出,三维建筑动画也必定有Maps Algorithm for Real Time Rendering []. Computer Science个质的飞跃,其艺术性和生动性浑然而生建筑动 and Technology.201,26(1:176-186上接第114页)3算法运行使用空间4结束语针对前面提出的新问题,我们可以基于如下思算法设计是软件开发的灵魂,不同的人可能设计想:对于处理一段在连续区间分布的整数,我们可以出不同的算法每种算法在执行时间和使用空间上可利用二进制位和位运算,通过公式运算将每个整数转能存在差异。在存储空间和程序运行时间要求苛刻的换到连续区间分布的某位二进制位上,从而实现存储情况下,就必须对各种算法进行分析,以期追求最优空间的压缩使用。如果系统存储一个整数需要2个字的算法。编写好的算法也是一个优秀程序设计人员所节,则新算法可以实现用1位代替2个字节;如果系追求的目标,笔者也想借此抛砖引玉,希望广大程序统存储一个整数需要4个字节,则新算法可以实现用设计人员设计出最优的算法。1位代替4个字节,具体算法如图3所示算法五函数模块。参考文献:01 void primes(unsigned n)[1]严蔚敏数据结构北京:清华大学出版社,200883 unsigned i,j,lenchar wa[2]黄维通 Visual C++面向对象与可视化程序设计北京:清华es if(n<2)return86 lensceil(n/8. 8)大学出版社,200107 arr=(char*)malloc(len)[3]杨勇虎数据结构C语言)第二版大连:东软电子出版社,99 for(i-2: i<=sqrt(n): 1+2012if(arIi/8]&(1(i88)))For(j-21: j