算法分析與優(yōu)化

福建電腦JJIAN COMPUTER算法分析與優(yōu)化茹小光(長(cháng)治醫學(xué)院計算機中心山西長(cháng)治046000【摘要】:本文介紹了筆者在程序設計過(guò)程中針對同一問(wèn)題的不同算法進(jìn)行分析,從算法執行的時(shí)間和算法運行使用的空間入手,對每種算法進(jìn)行分析比較,不斷改進(jìn)和優(yōu)化算法,以求獲得算法在運行時(shí)間和使用空間上的最優(yōu)?！娟P(guān)鍵詞】:算法;時(shí)間;空間;效率;因子1引言01for(1-2;1<=n;i+)在進(jìn)行程序設計時(shí),同一問(wèn)題可以用不同的算法03for(j-2;-;解決,而一個(gè)算法的質(zhì)量?jì)?yōu)劣將影響到程序運行的效玉f(ij==8)f1ag-1;8s if(flags)率。在存儲空間和程序運行時(shí)間要求苛刻的情況下07 printf("2d".1);就必須對各種算法進(jìn)行分析,其目的在于選擇合適算Flag法和改進(jìn)算法。算法分析主要是指分析算法的效率,它主要包含兩方面的內容:算法的運行時(shí)間和運行使圖1前三種算法采用結構用空間。我們可以通過(guò)對同一問(wèn)題的不同算法分析來(lái)其中,“口”處可依次用n-1、n/2、sqr(m)分別代替評價(jià)這些算法的優(yōu)劣。形成前面對應算法。2算法的運行時(shí)間上述三種算法采用的都是雙循環(huán)結構,無(wú)論是判一個(gè)算法執行所耗費的時(shí)間,從理論上是不能算斷單個(gè)數還是判斷完所有數,三種算法的運行次數顯出來(lái)的,必須上機運行測試才能知道。但我們不可能然是不同的,算法一執行次數最多,算法二位列其次,也沒(méi)有必要對每個(gè)算法都上機測試,我們可以通過(guò)算算法三執行次數最少。然而如果我們逆向思維,結合法花費的時(shí)間與算法中語(yǔ)句的執行次數成正比這種第三種算法思想,以范圍內所有整數的可能最簡(jiǎn)因子關(guān)系來(lái)判斷不同算法執行所耗費的時(shí)間的不同。下面作為外循環(huán),內循環(huán)采用排除法,排除那些因子倍數我們通過(guò)分析一個(gè)具體問(wèn)題的不同算法來(lái)說(shuō)明各種的非素數,最后剩下的便是我們所要的范圍內的所有算法的執行時(shí)間效率。素數,具體算法如圖2所示算法四函數模塊。問(wèn)題描述:求范圍[2,n內的所有素數(質(zhì)數)。01 void prime(unsigned n)眨2《算法一:判斷一個(gè)整數n是否是素數,可依次進(jìn)83 unsigned 1, j:行n/2,m3,…,m(m-1)試除,如果都沒(méi)有除盡,則n是51f(n<2)素數,否則n不是素數。簡(jiǎn)單說(shuō):就是試除到n的前87 arr=(int )malloc(n+1):08 For(1-2: i<-n: 1++)個(gè)數。arr[1]=118 for(i-2: i<-sgrt(n): 1++)f(arr[iD)算法二:判斷一個(gè)整數n是否是素數,可依次進(jìn)For(j2;=n;+1)行n/2,n/3,,n(m2)試除,如果都沒(méi)有除盡,則n是素arr[l-o14for(i2;i<-n;1*if(arr[i])數。否則n不是素數。簡(jiǎn)單說(shuō):就是試除到n的二分之printf("2d".1):ee(arr處算法三:判斷一個(gè)整數n是否是素數,可依次進(jìn)圖2算法四函數模塊行n2,n3,, n/sqrt(n)試除,如果都沒(méi)有除盡,則n是素算法四同算法三比較,算法執行的時(shí)間進(jìn)一步縮數;否則n不是素數。簡(jiǎn)單說(shuō):就是試除到n的開(kāi)平方短了,但帶*L「中國煤化工過(guò)程中增加了根處。內存空間的開(kāi)CNMHG為我們接下來(lái)上述三種算法都涉及到如下雙循環(huán)語(yǔ)句結構:需要改進(jìn)算法的自的在。下轉第119頁(yè))114·福建電腦2014年第1期福建電腦JIAN COMPUTER和皮膚還比較僵硬,動(dòng)物運動(dòng)的姿勢還不夠真實(shí),衣畫(huà)的前景一片光明。服隨著(zhù)人的運動(dòng)還不能真實(shí)反映其效果,氣候的變化要實(shí)時(shí)準確模擬還有很多路要走四;植物的3D動(dòng)畫(huà)效參考文獻:果更是重點(diǎn)的研究目標,還有圖形和圖像在動(dòng)態(tài)中融[1]程昌華,建筑動(dòng)畫(huà)的發(fā)展現狀叮],考試周刊,201246,合、情感在建筑物中的表現,以及美學(xué)、電影等表現手17-24法都是當前的研究方向吲[2]張志騰.淺析當前建筑漫游動(dòng)畫(huà)的優(yōu)勢與發(fā)展前景[J]絲綢之路,2009(8),79-80政府提倡加快城鎮建設,有政府的支持,建筑動(dòng)3李希,張行,三維動(dòng)畫(huà)在建筑設計中的運用一建筑動(dòng)畫(huà)產(chǎn)業(yè)作為新媒體環(huán)境下的新興產(chǎn)業(yè),應用越來(lái)越廣(4}傅建華,李侍琳,孔暉關(guān)于天津歷史風(fēng)晚建筑保護機制的泛,前景十分看好;在建筑設計、城鄉規劃、園林設計探索[C,第二屆歷史建筑遺產(chǎn)保護與可持續發(fā)展國際會(huì )議論和自然文化遺產(chǎn)保護等領(lǐng)域都具有強勁的競爭力。隨文集。天津:天津大學(xué)出版社,2010,34-36著(zhù)軟硬件技術(shù)的進(jìn)步,三維建筑動(dòng)畫(huà)設計和制作變得[5](美) eremy Birn譯者:吳洪濤,王華,等,圖形圖像:數字更為容易,用戶(hù)只要有一臺較高配置的個(gè)人電腦就繪圖中的光照與渲染[M.北京:電子工業(yè)出版社,2001可以參與到該行業(yè)的競爭,使得更多建筑動(dòng)畫(huà)的愛(ài)好[6]田美山淺談建筑動(dòng)畫(huà)的表現方法與優(yōu)勢冂、中國電子者和創(chuàng )業(yè)者加入到該行業(yè)中,這對我國的建筑動(dòng)畫(huà)的商務(wù)20130343發(fā)展和對國內動(dòng)畫(huà)整體水平的提升,更具有積極的意MsG, Wang Wo. Effectively Discriminating Fighting Shots義。同時(shí)隨著(zhù)力學(xué)、數字化、美學(xué)、音樂(lè )等元素的加入in Action Movies[JJ. Computer Science and Technology.2011, 26(1):187-194加上電影等表現手法應用到建筑的動(dòng)畫(huà)中,使得建筑8] LiangXH, Mas, CenLX,et al. Light Space Cascaded Shadow環(huán)境中的情感更加表現突出,三維建筑動(dòng)畫(huà)也必定有Maps Algorithm for Real Time Rendering []. Computer Science個(gè)質(zhì)的飛躍,其藝術(shù)性和生動(dòng)性渾然而生建筑動(dòng) and Technology.201,26(1:176-186上接第114頁(yè))3算法運行使用空間4結束語(yǔ)針對前面提出的新問(wèn)題,我們可以基于如下思算法設計是軟件開(kāi)發(fā)的靈魂,不同的人可能設計想:對于處理一段在連續區間分布的整數,我們可以出不同的算法每種算法在執行時(shí)間和使用空間上可利用二進(jìn)制位和位運算,通過(guò)公式運算將每個(gè)整數轉能存在差異。在存儲空間和程序運行時(shí)間要求苛刻的換到連續區間分布的某位二進(jìn)制位上,從而實(shí)現存儲情況下,就必須對各種算法進(jìn)行分析,以期追求最優(yōu)空間的壓縮使用。如果系統存儲一個(gè)整數需要2個(gè)字的算法。編寫(xiě)好的算法也是一個(gè)優(yōu)秀程序設計人員所節,則新算法可以實(shí)現用1位代替2個(gè)字節;如果系追求的目標,筆者也想借此拋磚引玉,希望廣大程序統存儲一個(gè)整數需要4個(gè)字節,則新算法可以實(shí)現用設計人員設計出最優(yōu)的算法。1位代替4個(gè)字節,具體算法如圖3所示算法五函數模塊。參考文獻:01 void primes(unsigned n)[1]嚴蔚敏數據結構北京:清華大學(xué)出版社,200883 unsigned i,j,lenchar wa[2]黃維通 Visual C++面向對象與可視化程序設計北京:清華es if(n<2)return86 lensceil(n/8. 8)大學(xué)出版社,200107 arr=(char*)malloc(len)[3]楊勇虎數據結構C語(yǔ)言)第二版大連:東軟電子出版社,99 for(i-2: i<=sqrt(n): 1+2012if(arIi/8]&(1(i88)))For(j-21: j