算法效率

對數(shù)據(jù)的邏輯結(jié)構(gòu)進行選擇，是構(gòu)造數(shù)學(xué)模型一大關(guān)鍵，而算法又是用來解決數(shù)學(xué)模型的。要使算法效率高，首先必須選好數(shù)據(jù)的邏輯結(jié)構(gòu)。選擇邏輯結(jié)構(gòu)的目的是提高信息的利用效果。在解決問題的過程中，選擇合理的邏輯結(jié)構(gòu)是相當重要的環(huán)節(jié)。

算法效率選擇合理的存儲結(jié)構(gòu)

數(shù)據(jù)的存儲結(jié)構(gòu)，分為順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。順序存儲結(jié)構(gòu)的特點是借助元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系；鏈式存儲結(jié)構(gòu)則是借助指示元素存儲地址的指針表示數(shù)據(jù)元素之間的邏輯關(guān)系。因為兩種存儲結(jié)構(gòu)的不同，導(dǎo)致這兩種存儲結(jié)構(gòu)在具體使用時也分別存在著優(yōu)點和缺點。 這里有一個較簡單的例子：我們需要記錄一個n×n的矩陣，矩陣中包含的非0元素為m個。 此時，我們?nèi)舨捎庙樞虼鎯Y(jié)構(gòu)，就會使用一個n×n的二維數(shù)組，將所有數(shù)據(jù)元素全部記錄下來；若采用鏈式存儲結(jié)構(gòu)，則需要使用一個包含m個結(jié)點的鏈表，記錄所有非0的m個數(shù)據(jù)元素。由這樣兩種不同的記錄方式，我們可以通過對數(shù)據(jù)的不同操作來分析它們的優(yōu)點和缺點。

1． 隨機訪問矩陣中任意元素。由于順序結(jié)構(gòu)在物理位置上是相鄰的，所以可以很容易地獲得任意元素的存儲地址，其復(fù)雜度為O(1)；對于鏈式結(jié)構(gòu)，由于不具備物理位置相鄰的特點，所以首先必須對整個鏈表進行一次遍歷，尋找需進行訪問的元素的存儲地址，其復(fù)雜度為O(m)。此時使用順序結(jié)構(gòu)顯然效率更高。

2． 對所有數(shù)據(jù)進行遍歷。兩種存儲結(jié)構(gòu)對于這種操作的復(fù)雜度是顯而易見的，順序結(jié)構(gòu)的復(fù)雜度為O(n2)，鏈式結(jié)構(gòu)為O(m)。由于在一般情況下m要遠小于n2，所以此時鏈式結(jié)構(gòu)的效率要高上許多。除上述兩種操作外，對于其它的操作，這兩種結(jié)構(gòu)都不存在很明顯的優(yōu)點和缺點，如對鏈表進行刪除或插入操作，在順序結(jié)構(gòu)中可表示為改變相應(yīng)位置的數(shù)據(jù)元素。 既然兩種存儲結(jié)構(gòu)對于不同的操作，其效率存在較大的差異，那么我們在確定存儲結(jié)構(gòu)時，必須仔細分析算法中操作的需要，合理地選擇一種能夠“揚長避短”的存儲結(jié)構(gòu)。

存儲結(jié)構(gòu)的選擇包括以下兩種。

一、合理采用順序存儲結(jié)構(gòu)。我們在平常做題時，大多都是使用順序存儲結(jié)構(gòu)對數(shù)據(jù)進行存儲。究其原因，一方面是出于順序結(jié)構(gòu)操作方便的考慮，另一方面是在程序?qū)崿F(xiàn)的過程中，使用順序結(jié)構(gòu)相對于鏈式結(jié)構(gòu)更便于對程序進行調(diào)試和查找錯誤。因此，大多數(shù)人習慣上認為，能夠使用順序結(jié)構(gòu)進行存儲的問題，最“好”采用順序存儲結(jié)構(gòu)。其實，這個所謂的“好”只是一個相對的標準，是建立在以下兩個前提條件之下的：

1． 鏈式結(jié)構(gòu)存儲的結(jié)點與順序結(jié)構(gòu)存儲的結(jié)點數(shù)目相差不大。這種情況下，由于存儲的結(jié)點數(shù)目比較接近，使用鏈式結(jié)構(gòu)完全不能體現(xiàn)出記錄結(jié)點少的優(yōu)點，并且可能會由于指針操作較慢而降低算法的效率。更有甚者，由于指針自身占用的空間較大，且結(jié)點數(shù)目較多，因而算法對空間的要求可能根本無法得到滿足。

2． 并非算法效率的瓶頸所在。由于不是算法最費時間的地方，這里是否進行改進，顯然是不會對整個算法構(gòu)成太大影響的，若使用鏈式結(jié)構(gòu)反而會顯得操作過于繁瑣。

二、必要時采用鏈式存儲結(jié)構(gòu)。

由于鏈式結(jié)構(gòu)中指針操作確實較繁瑣，并且速度也較慢，調(diào)試也不方便，因而大家一般都不太愿意用鏈式的存儲結(jié)構(gòu)。但是，這只是一般的觀點，當鏈式結(jié)構(gòu)確實對算法有很大改進時，我們還是不得不進行考慮的。

然而，如果我們采用的是鏈式存儲結(jié)構(gòu)，那么我們需要多少數(shù)據(jù)，就只會遍歷多少數(shù)據(jù)，這樣不僅充分發(fā)揮了鏈式存儲結(jié)構(gòu)的優(yōu)點，而且由于不需單獨對某一個數(shù)據(jù)進行提取，每次都是對所有數(shù)據(jù)進行判斷，從而避免了鏈式結(jié)構(gòu)的最大缺點。我們使用鏈式存儲結(jié)構(gòu)，雖然沒有降低問題的時間復(fù)雜度(鏈式存儲結(jié)構(gòu)在最壞情況下的存儲量與順序存儲結(jié)構(gòu)的存儲量幾乎相同)，但由于體現(xiàn)了前文所述選擇存儲結(jié)構(gòu)時揚長避短的原則，因而算法的效率也大為提高。我們選擇鏈式的存儲結(jié)構(gòu)，雖然操作上可能稍復(fù)雜一些，但由于改進了算法的瓶頸，算法的效率自然也今非昔比。由此可見，必要時選擇鏈式結(jié)構(gòu)這一方法，其效果是不容忽視的。

算法效率使用直接初始化

與直接初始化對應(yīng)的是復(fù)制初始化，什么是直接初始化？什么又是復(fù)制初始化？舉個簡單的例子，

ClassTestct1；ClassTestct2(ct1);//直接初始化ClassTestct3=ct1;//復(fù)制初始化

那么直接初始化與復(fù)制初始化又有什么不同呢？直接初始化是直接以一個對象來構(gòu)造另一個對象，如用ct1來構(gòu)造ct2，復(fù)制初始化是先構(gòu)造一個對象，再把另一個對象值復(fù)制給這個對象，如先構(gòu)造一個對象ct3，再把ct1中的成員變量的值復(fù)制給ct3，從這里，可以看出直接初始化的效率更高一點，而且使用直接初始化還是一個好處，就是對于不能進行復(fù)制操作的對象，如流對象，是不能使用賦值初始化的，只能進行直接初始化。可能我說得不太清楚，那么下面就引用一下經(jīng)典吧！

以下是Primer是的原話：

“當用于類類型對象時，初始化的復(fù)制形式和直接形式有所不同：直接初始化直接調(diào)用與實參匹配的構(gòu)造函數(shù)，復(fù)制初始化總是調(diào)用復(fù)制構(gòu)造函數(shù)。復(fù)制初始化首先使用指定構(gòu)造函數(shù)創(chuàng)建一個臨時對象，然后用復(fù)制構(gòu)造函數(shù)將那個臨時對象復(fù)制到正在創(chuàng)建的對象”，還有一段這樣說，“通常直接初始化和復(fù)制初始化僅在低級別優(yōu)化上存在差異，然而，對于不支持復(fù)制的類型，或者使用非explicit構(gòu)造函數(shù)的時候，它們有本質(zhì)區(qū)別：

ifstreamfile1("filename")://ok:directinitializationifstreamfile2="filename";//error:copyconstructorisprivate

算法效率盡量減少值傳遞，多用引用來傳遞參數(shù)。

如果參數(shù)是int等語言自定義的類型可能能性能的影響還不是很大，但是如果參數(shù)是一個類的對象，那么其效率問題就不言而喻了。例如一個判斷兩個字符串是否相等的函數(shù)，其聲明如下：

boolCompare（strings1,strings2)boolCompare(string*s1,string*s2)boolCompare(string&s1,string&s2)boolCompare(conststring&s1,conststring&s2)

其中若使用第一個函數(shù)（值傳遞），則在參數(shù)傳遞和函數(shù)返回時，需要調(diào)用string的構(gòu)造函數(shù)和析構(gòu)函數(shù)兩次（即共多調(diào)用了四個函數(shù)），而其他的三個函數(shù)（指針傳遞和引用傳遞）則不需要調(diào)用這四個函數(shù)。因為指針和引用都不會創(chuàng)建新的對象。如果一個構(gòu)造一個對象和析構(gòu)一個對象的開銷是龐大的，這就是會效率造成一定的影響。

然而在很多人的眼中，指針是一個惡夢，使用指針就意味著錯誤，那么就使用引用吧！它與使用普通值傳遞一樣方便直觀，同時具有指針傳遞的高效和能力。因為引用是一個變量的別名，對其操作等同于對實際對象操作，所以當你確定在你的函數(shù)是不會或不需要變量參數(shù)的值時，就大膽地在聲明的前面加上一個const吧，就如最后的一個函數(shù)聲明一樣。

同時加上一個const還有一個好處，就是可以對常量進行引用，若不加上const修飾符，引用是不能引用常量的。

算法效率減少除法運算的使用

無論是整數(shù)還是浮點數(shù)運算，除法都是一件運算速度很慢的指令，在計算機中實現(xiàn)除法是比較復(fù)雜的。所以要減少除法運算的次數(shù)，下面介紹一些簡單方法來提高效率：

1、通過數(shù)學(xué)的方法，把除法變?yōu)槌朔ㄟ\算，如if(a > b/c),如果a、b、c都是正數(shù)，則可寫成if(a*c > b)

2、讓編譯器有優(yōu)化的余地，如里你要做的運算是int型的n/8的話，寫成（unsigned)n/8有利于編譯器的優(yōu)化。而要讓編譯器有優(yōu)化的余地，則除數(shù)必須為常數(shù)，而這也可以用const修飾一個變量來達到目的。

算法效率避免使用多重繼承

在C 中，支持多繼承，即一個子類可以有多個父類。書上都會告訴我們，多重繼承的復(fù)雜性和使用的困難，并告誡我們不要輕易使用多重繼承。其實多重繼承并不僅僅使程序和代碼變得更加復(fù)雜，還會影響程序的運行效率。

這是因為在C 中每個對象都有一個this指針指向?qū)ο蟊旧?，而C 中類對成員變量的使用是通過this的地址加偏移量來計算的，而在多重繼承的情況下，這個計算會變量更加復(fù)雜，從而降低程序的運行效率。而為了解決二義性，而使用虛基類的多重繼承對效率的影響更為嚴重，因為其繼承關(guān)系更加復(fù)雜和成員變量所屬的父類關(guān)系更加復(fù)雜。

算法效率將小粒度函數(shù)聲明為內(nèi)聯(lián)函數(shù)

調(diào)用函數(shù)是需要保護現(xiàn)場，為局部變量分配內(nèi)存，函數(shù)結(jié)束后還要恢復(fù)現(xiàn)場等開銷，而內(nèi)聯(lián)函數(shù)則是把它的代碼直接寫到調(diào)用函數(shù)處，所以不需要這些開銷，但會使程序的源代碼長度變大。

所以若是小粒度的函數(shù)，如下面的Max函數(shù)，由于不需要調(diào)用普通函數(shù)的開銷，所以可以提高程序的效率。

intMax(inta,intb)
{
returna>b"J-main-content-end-dom">

算法效率定義

算法效率是指算法執(zhí)行的時間，算法執(zhí)行時間需通過依據(jù)該算法編制的程序在計算機上運行時所消耗的時間來度量。在現(xiàn)在的計算機硬件環(huán)境中，比較少需要考慮這個問題了，特別是pc機的編程，內(nèi)存空間越來越大，所以被考慮得也越來越少，不過一個好的程序員，都應(yīng)該對自己的程序有要求，每一個for比別人少一次判斷1000個for就能夠少掉很多的運行時間。所以能夠理解，能夠大概的去運用"效率度量"還是有很大意義的。

算法效率度量方法

度量一個程序的執(zhí)行時間通常有兩種方法：（一）事后統(tǒng)計的方法（二）事前分析估算的方法。

事后統(tǒng)計的方法不利于較大范圍內(nèi)的算法比較（異地，異時，異境）。

事前分析估算的方法與許多因素有關(guān)，包括算法本身選用的策略、問題的規(guī)模、書寫程序的語言、編譯產(chǎn)生的機器代碼質(zhì)量和機器執(zhí)行指令的速度等。為便于比較算法本身的優(yōu)劣，應(yīng)排除其它影響算法效率的因素。從算法中選取一種對于所研究的問題來說是基本操作的原操作，以該基本操作重復(fù)執(zhí)行的次數(shù)作為算法的時間量。（原操作在所有該問題的算法中都相同）

度量一個程序運行時間的方式通過時間復(fù)雜度和空間復(fù)雜度來表征。

上式表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和f(n)的增長率相同，稱作算法的漸近時間復(fù)雜度，簡稱時間復(fù)雜度。

上式表示空間復(fù)雜度。空間復(fù)雜度可以作為算法所需存儲空間的量度。若額外空間相對于輸入數(shù)據(jù)量來說是常數(shù)，則稱此算法為原地工作。原地工作意思是一個算法需要少量的輔助空間，且其大小不隨問題規(guī)模的大小而改變。如果所占空間量依賴于特定的輸入，則除特別指明外，均按最壞情況來分析 。

算法效率算法的最優(yōu)、最差和平均效率

最差效率：指當輸入規(guī)模為n時，算法的最壞情況下的效率。

最優(yōu)效率：指當輸入規(guī)模為n時，算法在最優(yōu)情況下的效率。

平均效率：指當輸入規(guī)模為n時，算法的平均效率。

大量實踐經(jīng)驗告訴我們，我們評價一個算法是應(yīng)該重點考慮最差效率這一點。

DFSA算法可采用各種方法預(yù)測待識別的標簽數(shù)量，然后動態(tài)調(diào)整最優(yōu)幀長，與FSA相比，系統(tǒng)效率有明顯改善，接近36．8%。但是，當標簽數(shù)量較多（特別是標簽數(shù)量大于500）時，采用由預(yù)測標簽數(shù)量設(shè)置最優(yōu)幀長的方案會使系統(tǒng)效率急劇下降。因此，在標簽數(shù)量較多的情況下，為了使系統(tǒng)效率得到提高，EPCClass1Gen2標準中采用了Q值算法，該算法可以實時自適應(yīng)地調(diào)整幀長 。

Q值算法

在Q值算法中，閱讀器首先發(fā)送Query命令，該命令中含有一個參數(shù)Q（取值范圍0～15），接收到命令的標簽可在[0，2Q－1]范圍內(nèi)（稱為幀長）隨機選擇時隙，并將選擇的值存入標簽的時隙計數(shù)器中，只有計數(shù)器為0的標簽才能響應(yīng)，其余標簽保持沉默狀態(tài)。當標簽接收到閱讀器發(fā)送的QueryRep命令時，將其時隙計數(shù)器減1，若減為0，則給閱讀器發(fā)送一個應(yīng)答信號。標簽被成功識別后，退出這輪盤存。當有兩個以上標簽的計數(shù)器都為0時，它們會同時對閱讀器進行應(yīng)答，造成碰撞。閱讀器檢測到碰撞后，發(fā)出指令將產(chǎn)生碰撞的標簽時隙計數(shù)器設(shè)為最大值（2Q－1），繼續(xù)留在這一輪盤存周期中，系統(tǒng)繼續(xù)盤存直到所有標簽都被查詢過，然后閱讀器發(fā)送重置命令，使碰撞過的標簽生成新的隨機數(shù) 。

根據(jù)上一輪識別的情況，閱讀器發(fā)送Query－Adjust命令來調(diào)整Q的值，當標簽接收到Query－Adjust命令時，先更新Q值，然后在[0，2Q－1]范圍內(nèi)選擇隨機值。EPCClass1Gen2標準中提供了一種參考算法來確定Q值的范圍.其中：Qfp為浮點數(shù)，其初值一般設(shè)為4．0，對Qfp四舍五入取整后得到的值即為Q；C為調(diào)整步長，其典型取值范圍是0．1

該算法在參數(shù)C的輔助下對Q值進行動態(tài)調(diào)整，但是C太大會造成Q值變化過于頻繁，導(dǎo)致幀長調(diào)整過于頻繁，C太小又不能快速地實現(xiàn)最優(yōu)幀長的選擇。因此，研究者們對Q值的調(diào)整進行了各種優(yōu)化 。

基于最大吞吐量調(diào)整Q值的算法

文獻提出一種基于最大吞吐量對Q值進行調(diào)整的算法，其中定義了以下變量：Nt為已識別的標簽個數(shù)；N為識別標簽所需的總時隙數(shù)；NC為沖突時隙的個數(shù)；nu為上一輪未識別的標簽個數(shù)；e為沖突時隙中的平均標簽個數(shù)；PC為沖突時隙所占的比例 。

這些參數(shù)之間的關(guān)系為PC=NC/N，e=nu/Nc，吞吐量=Nt/N。由于Aloha類算法的最大吞吐量為0．368（e－1）[5]，該算法以此作為調(diào)整Q值的依據(jù)。當系統(tǒng)吞吐量達到或接近0．368時，閱讀器僅需調(diào)用2Q－1次QueryRep命令，而不需要在接下來的盤存周期中調(diào)整Q值。當吞吐量小于0．368時，根據(jù)未識別的標簽個數(shù)nu來調(diào)整Q值 .

基于分組的位隙Aloha算法

文獻提出一種基于分組的位隙Aloha算法，該算法采用位隙Aloha算法中的128位預(yù)定序列，代表128個位隙。若某個標簽選擇了第i個位隙，則將第i位置1，其余各位都置0。當標簽數(shù)量為15時，位隙Aloha算法可獲得最大吞吐率88．38%，但隨著標簽數(shù)量的增加，算法性能急劇下降 。

因此，基于分組的位隙Aloha算法通過對標簽進行分組來提高算法的性能。該算法在查詢命令中設(shè)置了一個位隙計數(shù)器的參數(shù)Q（Q為整數(shù)，且0≤Q≤15），當標簽收到閱讀器發(fā)送的查詢命令后，在[0，2Q－1]范圍內(nèi)生成一個隨機數(shù)，即代表選擇了相應(yīng)的位隙，只有選擇了0的標簽才會立即響應(yīng)。同時，該算法根據(jù)沖突位隙數(shù)動態(tài)地對Q值進行調(diào)整：當沖突位隙數(shù)小于11時，Q減1且最小為0；當沖突位隙數(shù)在11～20之間時，Q保持不變；當沖突位隙數(shù)大于20時，Q加1且最大不超過15 。

綜上所述，基于Aloha的防碰撞算法原理簡單、容易實現(xiàn)，對新到達的標簽具有較好的適應(yīng)性，尤其對于標簽持續(xù)到達的情況有較好的解決方案，但該類算法存在幾個明顯的缺點：①響應(yīng)時間不確定，即同一批標簽在不同時刻進行識別所需要消耗的時間相差很大；②個別標簽可能永遠無法被識別；③Aloha算法達到最佳吞吐率的條件是其幀長等于標簽數(shù)量，當需要識別的標簽數(shù)量較多或選擇的幀長與實際待識別標簽數(shù)量不符時，系統(tǒng)性能將明顯下降。而基于樹的算法則很好地解決了這些問題 。

旋轉(zhuǎn)門算法除了平行四邊形算法之外，還能用三角形算法來表示。

效率與所取截面有關(guān)。取壓縮機進口截面和出口截面來計算效率,則為壓縮機的效率。如果不包括進出氣管在內(nèi),取壓縮機中第一級進口截面和末級出口截面計算效率,則為壓縮機級組的效率。如果取壓縮機的一個級的進口截面和出口截面計算效率,則為級的效率。 2100433B