影響算法效率的因素

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

2、存儲結構

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

例：稀疏矩陣的存儲和轉置算法

（1）存儲

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

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

#define MAXSIZE 12500

typedef struct{

int i,j;

ElemType e;

}Triple;

Typedef struct{

Triple data[MAXSIZE + 1];

int mu,nu,tu;

}TSMatrix;

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

（2）轉置

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

改進：矩陣的快速轉置算法

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

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

3、指針操作

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

4、查找的效率

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

哈希表

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

5.數據類型的選擇

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

6、存儲方式

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