影響算法效率的因素

1、從大的方面來講，所選擇的語言對算法的效率影響很大。一般來說，使用越高級的語言所需要的時間和空間就越大。另外，不同編譯器產(chǎn)生的代碼質(zhì)量不同，這對算法的效率也會有影響。

2、存儲結構

數(shù)據(jù)的存儲結構，分為順序存儲結構和鏈式存儲結構。順序存儲結構的特點是借助元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關系；鏈式存儲結構則是借助指示元素存儲地址的指針表示數(shù)據(jù)元素之間的邏輯關系。不同的問題求解選用不同的存儲結構。

例：稀疏矩陣的存儲和轉(zhuǎn)置算法

（1）存儲

如果采用數(shù)組的方式進行存儲，對稀疏矩陣來說有很多零元素，因而浪費空間嚴重，因此我們對稀疏矩陣進行壓縮存儲。只存儲稀疏矩陣的非零元素。在數(shù)據(jù)結構教材中用三元組表示方法，建立三元組順序表。

//..................................................................................................................

#define MAXSIZE 12500

typedef struct{

int i,j;

ElemType e;

}Triple;

Typedef struct{

Triple data[MAXSIZE + 1];

int mu,nu,tu;

}TSMatrix;

//....................................................................................

（2）轉(zhuǎn)置

直接進行轉(zhuǎn)置時，對要轉(zhuǎn)置的A表從第一行起掃描一遍，按照原矩陣的列序進行轉(zhuǎn)置，得到的新矩陣是以行序為主序的。但是這樣做只適合于非零元素的個數(shù)非常少的情況，否則和矩陣的直接轉(zhuǎn)置算法時間復雜度相差無幾。

改進：矩陣的快速轉(zhuǎn)置算法

附設兩個變量，num[col]表示矩陣中第col 列中非零元的個數(shù)，cpot[col]表示第col 列第一個非零元在b.data中的位置。

我們可以再矩陣轉(zhuǎn)置之前將我們附設的兩個變量都求出來，然后進行轉(zhuǎn)置，即為快速轉(zhuǎn)置算法。

3、指針操作

在使用指針時，指針的有秩序掃描非常重要。例如在模式匹配中，如果直接進行匹配，當有不完全匹配時，主串的指針需要回溯。在KMP算法中，我們先可以求出每個元素的next函數(shù)值，從而在發(fā)生不完全匹配時，主串的指針不必要回溯，只需要模式串的元素回到當前元素的next函數(shù)值所指的元素再進行匹配即可。當主串和模式串有很多不完全匹配時，KMP算法可以大大提高效率。

4、查找的效率

有很多快速查找的算法都可以提高查找的效率，如建立索引，折半查找等，都是在記錄和關鍵字之間進行比較，從而尋求關系。這一類查找建立在比較的基礎之上。查找的效率依賴于查找過程中所進行的比較次數(shù)。

哈希表

在哈希表中，使得記錄的存儲位置和關鍵字之間建立一個確定的存儲關系，因而在查找時，只需要根據(jù)這個對應的關系f 找到給定值K 的像f(k)。用這個思想建立哈希表。如在基因組匹配時，用哈希表非常方便。

5.數(shù)據(jù)類型的選擇

數(shù)據(jù)類型的選擇也會影響算法效率，在對時間和空間要求非常嚴格時，盡可能的使用占用空間較小的數(shù)據(jù)類型。使用動態(tài)開辟空間會使得效率降低，所有在能確定或估計出需要的空間大小的情況下盡量使用靜態(tài)數(shù)字。個人覺得用vector雖然方便，但是效率并不高。

6、存儲方式

用堆操作還是用棧操作，對于不同的問題需要仔細選擇。在串和隊列的有關操作中用堆操作合適，在樹的操作中用棧操作合適，如建立二叉樹中序遍歷的遞歸算法或非遞歸算法，用棧操作好。