演算法設計的時間空間權衡原則

❶ 演算法復雜度：時間復雜度和空間復雜度

本文部分摘抄於此
演算法復雜度分為時間復雜度和空間復雜度。
時間復雜度是指執行演算法所需要的計算工作量；
而空間復雜度是指執行這個演算法所需要的內存空間。
（演算法的復雜性體現在運行該演算法時的計算機所需資源的多少上，計算機資源最重要的是時間和空間（即寄存器）資源，因此復雜度分為時間和空間復雜度）。

一個演算法執行所耗費的時間，從理論上是不能算出來的，必須上機運行測試才能知道。但我們不可能也沒有必要對每個演算法都上機測試，只需知道哪個演算法花費的時間多，哪個演算法花費的時間少就可以了。並且一個演算法花費的時間與演算法中語句的執行次數成正比例，哪個演算法中語句執行次數多，它花費時間就多。一個演算法中的語句執行次數稱為語句頻度或時間頻度。記為T(n)。

在剛才提到的時間頻度中，n稱為問題的規模，當n不斷變化時，時間頻度T(n)也會不斷變化。但有時我們想知道它變化時呈現什麼規律。為此，我們引入時間復雜度概念。 一般情況下，演算法中基本操作重復執行的次數是問題規模n的某個函數，用T(n)表示，若有某個輔助函數f(n),使得當n趨近於無窮大時， T(n)/f(n) 的極限值為不等於零的常數，則稱f(n)是T(n)的同數量級函數。記作 T(n)=O(f(n)), 稱 O(f(n)) 為演算法的漸進時間復雜度，簡稱時間復雜度。

並且一個演算法花費的時間與演算法中語句的執行次數成正比例，哪個演算法中語句執行次數多，它花費時間就多。一個演算法中的語句執行次數稱為語句頻度或時間頻度。記為T(n)。

演算法中執行次數最多的那條語句就是基本語句，通常是最內層循環的循環體。

只需計算基本語句執行次數的數量級，這就意味著只要保證基本語句執行次數的函數中的最高次冪正確即可，可以忽略所有低次冪和最高次冪的系數。這樣能夠簡化演算法分析，並且使注意力集中在最重要的一點上：增長率。

將基本語句執行次數的數量級放入大Ο記號中。

如果演算法中包含嵌套的循環，則基本語句通常是最內層的循環體，如果演算法中包含並列的循環，則將並列循環的時間復雜度相加。

第一個for循環的時間復雜度為Ο(n)，第二個for循環的時間復雜度為Ο( n 2)，則整個演算法的時間復雜度為Ο(n+ n 2)=Ο( n 2)。

Ο(1)表示基本語句的執行次數是一個常數，一般來說，只要演算法中不存在循環語句，其時間復雜度就是Ο(1)。其中 Ο(log2n)、Ο(n)、 Ο(nlog2n)、Ο(n2)和Ο(n3) 稱為多項式時間， 而Ο(2n)和Ο(n!)稱為指數時間 。計算機科學家普遍認為前者（即多項式時間復雜度的演算法）是有效演算法，把這類問題稱為 P（Polynomial,多項式）類問題 ，而把後者（即指數時間復雜度的演算法）稱為 NP（Non-Deterministic Polynomial, 非確定多項式）問題 。

（4）在計算演算法時間復雜度時有以下幾個簡單的程序分析法則:

(1).對於一些簡單的輸入輸出語句或賦值語句,近似認為需要O(1)時間

(2).對於順序結構,需要依次執行一系列語句所用的時間可採用大O下"求和法則"

求和法則:是指若演算法的2個部分時間復雜度分別為 T1(n)=O(f(n))和 T2(n)=O(g(n)),則 T1(n)+T2(n)=O(max(f(n), g(n)))

特別地, 若T1(m)=O(f(m)), T2(n)=O(g(n)),則 T1(m)+T2(n)=O(f(m) + g(n))

(3).對於選擇結構,如if語句,它的主要時間耗費是在執行then字句或else字句所用的時間,需注意的是檢驗條件也需要O(1)時間

(4).對於循環結構,循環語句的運行時間主要體現在多次迭代中執行循環體以及檢驗循環條件的時間耗費,一般可用大O下"乘法法則"

乘法法則 : 是指若演算法的2個部分時間復雜度分別為 T1(n)=O(f(n))和 T2(n)=O(g(n)),則T1 * T2=O(f(n) * g(n))

(5).對於復雜的演算法,可以將它分成幾個容易估算的部分,然後利用求和法則和乘法法則技術整個演算法的時間復雜度

另外還有以下2個運演算法則:(1) 若g(n)=O(f(n)),則O(f(n))+ O(g(n))= O(f(n))；(2) O(Cf(n)) = O(f(n)),其中C是一個正常數

（5）下面分別對幾個常見的時間復雜度進行示例說明：

(1)、O(1)

​ Temp=i; i=j; j=temp;

以上三條單個語句的頻度均為1，該程序段的執行時間是一個與問題規模n無關的常數。演算法的時間復雜度為常數階，記作T(n)=O(1)。 注意：如果演算法的執行時間不隨著問題規模n的增加而增長，即使演算法中有上千條語句，其執行時間也不過是一個較大的常數。此類演算法的時間復雜度是O(1)。

(2)、O(n2)

2.1. 交換i和j的內容

解： 因為Θ(2n2+n+1)=n2（Θ即：去低階項，去掉常數項，去掉高階項的常參得到），所以T(n)= =O(n2)；

2.2.

​

解： 語句1的頻度是n-1

一般情況下，對步進循環語句只需考慮循環體中語句的執行次數，忽略該語句中步長加1、終值判別、控制轉移等成分，當有若干個循環語句時，演算法的時間復雜度是由嵌套層數最多的循環語句中最內層語句的頻度f(n)決定的。

(3)、O(n)

解：

(4)、O(log2n)

解：

(5)、O(n3)

解：

（5）常用的演算法的時間復雜度和空間復雜度

一個經驗規則： 其中c是一個常量，如果一個演算法的復雜度為c 、 log2n 、n 、 n log2n ,那麼這個演算法時間效率比較高 ，如果是 2n * , 3n ,n!，那麼稍微大一些的n就會令這個演算法不能動了，居於中間的幾個則差強人意。

​ 演算法時間復雜度分析是一個很重要的問題，任何一個程序員都應該熟練掌握其概念和基本方法，而且要善於從數學層面上探尋其本質，才能准確理解其內涵。

2、演算法的空間復雜度

​ 類似於時間復雜度的討論，一個演算法的空間復雜度(Space Complexity)S(n)定義為該演算法所耗費的存儲空間，它也是問題規模n的函數。漸近空間復雜度也常常簡稱為空間復雜度。

空間復雜度(Space Complexity)是對一個演算法在運行過程中臨時佔用存儲空間大小的量度。一個演算法在計算機存儲器上所佔用的存儲空間，包括存儲演算法本身所佔用的存儲空間，演算法的輸入輸出數據所佔用的存儲空間和演算法在運行過程中臨時佔用的存儲空間這三個方面。

演算法的輸入輸出數據所佔用的存儲空間是由要解決的問題決定的，是通過參數表由調用函數傳遞而來的，它不隨本演算法的不同而改變。存儲演算法本身所佔用的存儲空間與演算法書寫的長短成正比，要壓縮這方面的存儲空間，就必須編寫出較短的演算法。

演算法在運行過程中臨時佔用的存儲空間隨演算法的不同而異，有的演算法只需要佔用少量的臨時工作單元，而且不隨問題規模的大小而改變，我們稱這種演算法是「就地"進行的，是節省存儲的演算法，如這一節介紹過的幾個演算法都是如此；

有的演算法需要佔用的臨時工作單元數與解決問題的規模n有關，它隨著n的增大而增大，當n較大時，將佔用較多的存儲單元，例如將在第九章介紹的快速排序和歸並排序演算法就屬於這種情況。

如當一個演算法的空間復雜度為一個常量，即不隨被處理數據量n的大小而改變時，可表示為O(1)；當一個演算法的空間復雜度與以2為底的n的對數成正比時，可表示為O(log2n)；當一個演算法的空I司復雜度與n成線性比例關系時，可表示為O(n).

【1】如果演算法的執行時間不隨著問題規模n的增加而增長，即使演算法中有上千條語句，其執行時間也不過是一個較大的常數。此類演算法的時間復雜度是O(1)。

解答：
T(n)=O(1)，
這個程序看起來有點嚇人，總共循環運行了1100次，但是我們看到n沒有?
沒。這段程序的運行是和n無關的，
就算它再循環一萬年，我們也不管他，只是一個常數階的函數

【2】當有若干個循環語句時，演算法的時間復雜度是由嵌套層數最多的循環語句中最內層語句的頻度f(n)決定的。

該程序段中頻度最大的語句是(5)，內循環的執行次數雖然與問題規模n沒有直接關系，但是卻與外層循環的變數取值有關，而最外層循環的次數直接與n有關，因此可以從內層循環向外層分析語句(5)的執行次數：
則該程序段的時間復雜度為T(n)=O(n3/6+低次項)=O(n3)

【3】演算法的時間復雜度不僅僅依賴於問題的規模，還與輸入實例的初始狀態有關。

在數值A[0..n-1]中查找給定值K的演算法大致如下：

此演算法中的語句(3)的頻度不僅與問題規模n有關，還與輸入實例中A的各元素取值及K的取值有關:

（5）時間復雜度評價性能

有兩個演算法A1和A2求解同一問題，時間復雜度分別是T1(n)=100n2，T2(n)=5n3。
（1）當輸入量n＜20時，有T1(n)＞T2(n)，後者花費的時間較少。
（2）隨著問題規模n的增大，兩個演算法的時間開銷之比5n3/100n2=n/20亦隨著增大。
即當問題規模較大時，演算法A1比演算法A2要有效地多。它們的漸近時間復雜度O(n2)和O(n3)從宏觀上評價了這兩個演算法在時間方面的質量。

在演算法分析時，往往對演算法的時間復雜度和漸近時間復雜度不予區分，而經常是將漸近時間復雜度T(n)=O(f(n))簡稱為時間復雜度，其中的f(n)一般是演算法中頻度最大的語句頻度。

其實生活很美好，只是你想的太多了。沒有，不會，有差距很正常，因為我不會

❷ 演算法的設計原則是什麼

1.窮舉演算法思想

窮舉演算法思想就是從所有的可能結果中一個一個的試驗，知道試出正確的結果。具體的操作步驟如下：

1)對每一種可能的結果，計算其結果；

2)判斷結果是否符合題目要求，如果符合則該結果正確，如果不符合則繼續進行第1)步驟。

窮舉演算法思想的經典例子為雞兔同籠為題（又稱龜鶴同籠問題），題目為「一個籠子里有雞兔，共15個頭、46條腿，問雞兔各有多少只？」。代碼如下：

public static void main(String[] args) {

int head = 0;
int leg = 0;
System.out.println( "輸入雞兔頭數：");
Scanner input=new Scanner(System.in);
head = input.nextInt();
System.out.println( "輸入雞兔腿數：");
Scanner input1=new Scanner(System.in);
leg = input1.nextInt();

boolean existence = false;
for( int i = 0; i <= head; i++){
if( 2 * i + 4 * ( head - i) == leg){
System.out.println( "雞的個數 :" + i);
System.out.println( "兔的個數 :" + ( head - i));
existence = true;
}
}

if( !existence){
System.out.println( "你輸入的數據不正確");
}
}

2.遞推演算法思想

遞推演算法演算法就是根據已知條件，利用特定關系推導出中間推論，直到得到結果的演算法。

遞推演算法思想最經典的例子是斐波那契數列 : 1,1,2,3,5,8,13......

上面的數列符合F(n) = F(n-1) + F(n-2).代碼如下：

public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int n = input.nextInt();
System.out.println( fibonacci( n));
}

public static int fibonacci( int n){
if( n == 1){
return 1;
}else if( n == 2){
return 1;
}else{
return fibonacci( n - 1) + fibonacci( n - 2);
}
}

3.遞歸演算法思想

遞歸演算法思想是把大問題轉換成同類問題的子問題，然後遞歸調用函數表示問題的解。

在使用遞歸的時候一定要注意調回遞歸函數的終止條件。

遞歸演算法比較經典的例子是求階乘。代碼如下：

public static void main(String[] args) {
System.out.println( "輸入一個大於零的數：");
Scanner input=new Scanner(System.in);
int n = input.nextInt();
System.out.println( factorial( n));
}

public static int factorial( int n){
if( n == 0){
return 1;
}else if( n == 1){
return 1;
}else{

❸ 設計演算法的原則

設計演算法的原則：

1、正確性：演算法的正確性是指演算法至少應該具有輸入、輸出和加工處理無歧義性、能正確反映問題的需要、能夠得到問題的正確答案。

2、可讀性：設計演算法的目的，一方面是為了讓計算機執行，但還有一個重要的目的就是為了便於他人的閱讀，讓人理解和交流，自己將來也可閱讀。如果可讀性不好，時間長了自己都不知道寫了什麼，可讀性是評判演算法（也包括實現它的程序代碼）好壞很重要的標志。

3、健壯性：當輸入的數據非法時，演算法應當恰當地做出反應或進行相應處理，而不是莫名其妙的輸出結果。並且處理出錯的方法不應是中斷程序的執行，而應是返回一個表示錯誤或錯誤性質的值，以便於在更高的抽象層次上進行處理。

4、高效率與低存儲量：通常，演算法的效率指的是演算法的執行時間；演算法的存儲量指的是演算法執行過程中所需要的最大存儲空間，兩者的復雜度都與問題的規模有關。演算法分析的任務是對設計的每一個具體的演算法，利用數學工具，討論其復雜度，探討具體演算法對問題的適應性。

(3)演算法設計的時間空間權衡原則擴展閱讀：

演算法的「正確」通常在用法上有很大的差別，大體分為以下4個層次：

1、演算法程序沒有語法錯誤；

2、演算法程序能夠根據正確的輸入的值得到滿足要求的輸出結果；

3、演算法程序能夠根據錯誤的輸出的值滿足規格說明的輸出結果；

4、演算法程序對於精心設計、極其刁難的測試數據都能滿足要求的輸出結果。

對於這4層含義，層次要求最低，因為僅僅沒有語法錯誤實在談不上是好的演算法。而層次（4）是最困難的，人們幾乎不可能逐一驗證所有的輸入都得到正確的結果。因此，演算法的正確性在大部分情況下都不可能用程序來證明，而是用數學方法證明的。

❹ 演算法設計原則是什麼

原則：首先說設計的演算法必須是"正確的"，其次應有很好的"可讀性"，還必須具有"健壯性"，最後應考慮所設計的演算法具有"高效率與低存儲量"。

所謂演算法是正確的，除了應該滿足演算法說明中寫明的"功能"之外，應對各組典型的帶有苛刻條件的輸入數據得出正確的結果。

在演算法是正確的前提下，演算法的可讀性是擺在第一位的，這在當今大型軟體需要多人合作完成的環境下是換重要的，另一方面，晦澀難讀的程序易於隱藏錯誤而難以調試。演算法的效率指的是演算法的執行時間，演算法的存儲量指的是演算法執行過程中所需最大存儲空間。

演算法是程序設計的另一個不可缺的要素，因此在討論數據結構的同時免不了要討論相應的演算法。這里有兩重意思，即演算法中的操作步驟為有限個，且每個步驟都能在有限時間內完成。

確定性表現在對演算法中每一步的描述都沒有二義性，只要輸入相同，初始狀態相同，則無論執行多少遍，所得結果都應該相同。

可行性指的是，序列中的每個操作都是可以簡單完成的，其本身不存在演算法問題，例如，"求x和y的公因子"就不夠基本。

輸入值即為演算法的操作對象，但操作的對象也可以由演算法自身生成，如"求100以內的素數"，操作對象是自然數列，可以由變數逐個增1生成。

演算法的健壯性指的是，演算法應對非法輸入的數據作出恰當反映或進行相應處理，一般情況下，應向調用它的函數返回一個表示錯誤或錯誤性質的值。

❺ 一文講透演算法中的時間復雜度和空間復雜度計算方式

作為一名「程序猿」，大家應該都聽過這么一句話：程序=數據結構+演算法。

這句話是由瑞士計算機科學家尼古拉斯·沃斯（Niklaus Wirth）在 1984 年獲得圖靈獎時說的一句話，這位大佬還以這句話為名出了一本書《Algorithms + Data Structures=Programs》，從此這句話就成為了大家耳熟能詳的一句名言。

隨著時間的推移，不管這句話是不是非常准確，但至少能說明數據結構與演算法對程序來說是非常核心的基礎，如果我們想要寫出更多優秀優雅的代碼，那麼數據結構與演算法是必須要掌握好的。

很多人可能覺得，我不會演算法，代碼一樣寫得很"溜"，演算法這東西似乎用處不大。現在互聯網的發達，我們想要什麼幾乎都可以在網上找到現成的，各種框架功能十分強大，似乎看起來確實不用演算法也可以寫出「好代碼」。然而假如我們不懂演算法，比如項目中用到了排序，我們如何評估代碼的執行效率？再比如最常用的 ArrayList 和 LinkedList ，我們該如何選擇，又比如說我們需要去集合中找某一個數，又該如何寫出性能優秀的代碼呢？

同樣的代碼，如何判斷誰的代碼是優秀的代碼？可讀性，可擴展性，健壯性可能都可以用來判定，然而這些東西我覺得並不能直接體現出你代碼的優秀，因為對用戶而言，訪問你的代碼響應速度快那就是優秀的代碼，相反，動輒響應幾秒甚至更長時間的介面，恐怕就算你可讀性再好，再健壯也稱不上是好代碼。

所以說一段代碼是否優秀，最直接的判斷標准就是性能，而如果要寫出高性能的代碼，那麼就必須要了解演算法，而且拋開這個因素，但凡不想一輩子都寫 CRUD 代碼的，也需要去了解演算法，我們使用的很多框架和中間件底層都有數據結構和演算法的身影，學好演算法對我們源碼閱讀時理解其設計思想也是大有裨益的。

要說功利性的目的，那就是面試，目前很多大廠的面試，演算法基本必面，所以想進大廠的話，咱們也得好好學學演算法。

提到演算法，很多人的第一反應就是太難學了，學不會，或者說經常是看完就忘了，但是其實對於我們一個普通的開發者而言，因為並不需要我們去發明演算法，我們需要的僅僅只是去靈活的運用演算法，所以並不需要非常扎實的數據基礎，當然基本的數學常識還是要有的。

如果說需要去發明設計一款演算法，那就要去推導去證明演算法的可行性，這種是需要具有非常扎實的數學基礎的，一般人確實無法做到，然而我們普通程序員口中提到演算法無非是二分查找法，哈希演算法等，高級一點的就還有回溯，貪心，動態規劃等等，這些所謂的演算法都是已經有現成的公式了，我們要做的無非就是理解它，然後靈活的運用它。這就和我們以前學習數學公式一樣，給你一個公式，然後你去做題，做題的過程其實就是去靈活地運用這個公式。

演算法也是同理，都是有特定方法和特定思路的，我們也並不需要去推導證明這種方式為什麼可行，所以學習演算法沒有其他訣竅，就是先理解思路，然後多練，等熟練了，自然就可以靈活運用了，也不會說學了立刻就忘了。學完就忘無非兩個原因，一是沒理解，二是沒有練習鞏固。

數據結構與演算法經常是放在一起講，這兩者是沒辦法獨立的，因為演算法是為了達到某種目的的一種實現方式，而數據結構是一種載體，也就是說演算法必須依賴數據結構這種載體，否則就是空談。換句話說：數據結構是為演算法服務的，而演算法又需要作用在特定的數據結構之上。

一個演算法到底好不好，我們如何去評價？前面我們提到了，你的代碼好不好，最直觀的就是看響應速度，演算法也一樣，同樣實現一個目的（比如說排序），誰的演算法速度快，我們就可以認為誰的演算法更優，如果說兩種演算法實現的速度差不多，那麼我們還可以去評價演算法所佔用的空間，誰佔用的空間少，那麼就可以認為誰的演算法更優，這就是演算法的基礎：時間復雜度和空間復雜度。

學習演算法之前，我們必須要學會如何分析時間復雜度和空間復雜度（也就是「快」和「省」），否則自己寫出來的演算法自己都不知道演算法的效率。

接觸過演算法的都知道，演算法的時間復雜度是用大寫的「O」來表示的，比如： O(1) ， O(n) ， O(logn) ， O(nlogn) ， O(n²) 等等。

變數指的是變數，也就是一段代碼的執行時間是隨著變數的變化而變化的，而不變指的是常量，也就是不論我的變數如何改變，執行時間都不會改變。

接下來我們就實際的來分析下常用時間復雜度的例子來練習一下。

0(1) 復雜度演算法也稱之為常數階演算法。這里的 1 是用來代指常量，也就是說這個演算法的效率是固定的，無論你的數據量如何變化，效率都一樣，這種復雜度也是最優的一種演算法。

上面的示例中不論有多少行代碼，時間復雜度都是屬於常數階段。換言之：只要代碼不存在 循環 ， 遞歸 等循環類調用，不論代碼有多少行，其復雜度都是常數階。

O(n) 復雜度演算法也稱之為線性階段。比如下面這個示例我們應該怎麼分析復雜度呢？

前面常量階沒分析是因為常量階比較容易理解，接下來我們就以線性階這個為例子來分析下具體是怎麼得到的。

我們假設每一行代碼的執行時間是 T ，那麼上面這段代碼的執行復雜度是多少呢？

答案很明顯，那就是 T+n*T ，也就是 (n+1)T ，而在演算法中有一個原則，那就是常量可以被忽略，所以就得到了 nT ，換成大 O 表示法就是 O(n) 。

這只是一個簡略的計算過程，大家也不用較真說每行代碼執行時間可能不一樣之類的，也不要較真說 for 循環佔用了一行，下面的大括弧也佔用了一行，如果要較真這個，那我建議可以去想一下 1=1 為什麼等於 2 。

演算法中的復雜度反應的只是一個趨勢，這里 O(n) 反應的就是一個趨勢，也就是說隨著 n 的變化，演算法的執行時間是會降低的。

知道了上面的線性階，那麼平方階就很好理解了，雙層循環就是平方階，同理，三次循環就是立方階， k 次循環就是 k 次方階。

O(logn) 也稱之為對數階，對數階也很常見，像二分查找，二叉樹之類的問題中會見到比較多的對數階復雜度，但是對數階也是比較難理解的一種演算法復雜度。

下面我們還是來看一個例子：

這段代碼又該如何分析復雜度呢？這段代碼最關鍵的就是要分析出 while 循環中到底循環了多少次，我們觀察這個循環，發現 i 並不是逐一遞增，而是不斷地翻倍： 1->2->4->8->16->32->64 一直到等於 n 為什麼才會結束，所以我們得到了這樣的一個公式： 2^x=n 。

也就是說我們只要計算出 x 的值，就得到了循環次數，而根據高中的數學知識我們可以得到 x=log2n （ 2 在下面，是底數，試了幾種方法都打不出來，放棄了），所以根據上面線性階的分析方法，我們省略常量，就得到了示例中的演算法復雜度為 O(log2n) 。

同樣的分析方式，下面的例子，我們可以很快地分析出復雜度就為 O(log3n) ：

上面得到的 log3n 我們可以再做進一步的轉換： log3n=log32 * log2n ，而 log32 （注意這幾個地方的情況 3 是底數，在下面） 是一個常量，常量可以省略，所以也就得到了： O(log3n)=O(log2n) 。同樣的道理，不論底數是多少，其實最終都可以轉化成和 O(log2n) 相等，正因為如此，為了方便，我們演算法中通常就會省略底數，直接寫作 O(logn) 。

上面的數學公式大家如果忘了或者看不懂也沒關系，只要記住不論對數的底數是多少，我們都算作 O(logn) ，而對於一個演算法的復雜度是否是對數階，還有一個簡易的判斷方法： 當循環中下標以指定倍數形式衰減，那麼這就是一個對數階 。

如果理解了上面的對數階，那麼這種線性對數階就非常好理解了，只需要在對數階的演算法中再嵌一層循環就是線性對數階：

分析了前面這些最常用的時間復雜度，其實我們可以得到以下規律：

除了上面常用的復雜度之外，另外還有指數階，階層階，根號階等，這些接觸的相對會較少，我們就不特意做分析了，如果大家感興趣的話，可以自己去了解下。

前面我們分析的都是只有一段代碼比較復雜的情況下得到的復雜度結果，那麼假如我一個演算法中，有多段代碼都比較復雜呢？這時候復雜度該如何分析？

我們先看下面這個例子：

這個例子中有三個循環，首先第一個，是一個常量，那麼根據前面的結論，不論這個常量是多大，都屬於常量級，所以第一個循環中的復雜度為 O(1) ，第二個和第三個循環我們前面也分析過，復雜度分別為 O(n) 和 O(n²) 。

也就是這一段代碼中有三段代碼產生了三種不同復雜度，而且這三個復雜度可以很明顯得到的大小關系為： O(1)<o(n)<o(n²) span=""> </o(n)<o(n²)> ，像這種在同一個演算法中有明確大小關系的，我們就可以直接取最大值作為這個演算法的復雜度，所以這個例子中演算法的復雜度就是 O(n²) 。

接下來我們再來看一個例子：

這個例子我們同樣對三段循環分別分析可以分別得到如下復雜度： O(1) ， O(m) ， O(n) 。這時候我們只能知道 O(1) 最小可以忽略，但是後面兩個無法卻無法確定大小，所以這時候我們需要取兩段循環復雜度之和來作為演算法的復雜度，所以可以得到這個例子的演算法復雜度為： O(m+n) 。

上面分析的時間復雜度都是比較簡單的，實際演算法中可能會比示例中復雜的多，而且我們示例中只要是循環都是無腦循環，也就是一定從頭循環到尾，然而實際中我們有時候並不需要從頭循環到尾，可能中途就會結束循環，所以我們根據實際情況，又可以將時間復雜度從以下四個方面來進一步分析：

這四種類型的時間復雜度在這里只會介紹前面三種，因為第四種比較復雜，而且使用場景也非常有限，而且對於這四種復雜度的分析，大家也作為了解就可以，不敢興趣的朋友們可以跳過這一小部分，因為在絕大部分情況我們只需要分析最壞復雜度就行，也就是假設循環全部執行完畢場景下的時間復雜度。

我們通過一個例子來理解下最好時間復雜度：

這個方法就是在一個指定數組中找到指定元素的下標，找不到就返回 -1 ，這個方法比較簡單，應該比較好理解。

注意這個方法中的循環體，如果找到元素，那麼就直接返回，這就會有一個現象，那就是我這個循環體到底會循環多少次是不確定的，可能是 1 次，也可能是 n （假設數組的長度） 次，所以假如我們要找的元素就在數組中的第一個位置，那麼我循環一次就找到了，這個演算法的復雜度就是 O(1) ，這就是最好情況時間復雜度。

理解了最好時間復雜度，那麼最壞時間復雜度也很好理解了，那就是數組中不存在我要找到元素，或者說最後一個值才是我要找的元素，那麼這樣我就必須循環完整個數組，那麼時間復雜度就是 O(n) ，這也就是最壞時間復雜度。

最好時間復雜度和最壞時間復雜度畢竟只有特殊情況才會發生，概率還是相對較小，所以我們很容易就想到我們也需要有一個平均時間復雜度。

我們簡單的來分析一下，為了便於分析，我們假設一個元素在數組和不在數組中的概率都為 1/2 ，然後假如在數組在，那麼又假設元素出現在每個位置的概率也是一樣的，也就是每個位置出現元素的概率為： 1/n 。

所以最終得到的平均時間復雜度應該等於元素在數組中和元素不在數組中兩種情況相加。

因為元素在數組中的概率為 1/2 ，然後在每個位置出現的概率也為 1/n 。假如元素出現在第一個位置，復雜度為 1*(1/2n) ；假如元素出現在第二個位置，復雜度為 2 * (1/2n) ，最終得到當前場景下時間復雜度為： 1*(1/2n) + 2 * (1/2n) + ... + n*(1/2n) =(n+1)/4。

前面已經假定了元素不在數組中的概率為 1/2 ，所以當前場景下的時間復雜度為： n * (1/2) ，因為元素不在數組中，那麼這個演算法必然會將整個循環執行完畢，也就循環是 n 次。

最後我們把兩種情況的復雜度之和相加就得到了平均時間復雜度： (n+1)/4 + n/2 = (3n+1)/4 ，最終我們將常數類的系數忽略掉，就得到了平均時間復雜度為 O(n) 。

均攤時間復雜度的演算法需要使用攤還分析法，計算方式相對有點復雜，而且使用場景很有限，本文就不做過多介紹了。

空間復雜度全稱就是漸進空間復雜度，用來表示演算法的存儲空間與數據規模之間的增長關系。和時間復雜度一樣，空間復雜度也是用大 O 進行表示。

其實學會了分析時間復雜度，那麼空間復雜度的分析就簡單了，主要就看我們在一個演算法當中到底有沒有使用到了額外的空間來進行存儲數據，然後判斷這個額外空間的大小會不會隨著 n 的變化而變化，從而得到空間復雜度。

我們來看一個給數組賦值例子，假設這就是一個演算法，我們可以來分析下這個演算法的空間復雜度：

一開始定義了一個變數，這里需要空間，但是這是一個常量級的（不隨 n 的變化而變化），然後再定義了一個數組，數組的長度為 n ，這里數組也需要佔用空間，而且數組的空間是隨著 n 的變化而變化的，其餘代碼沒有佔用額外空間，所以我們就可以認為上面示例中的空間復雜度為 O(n) 。

對於演算法的空間復雜度也可以簡單的進行總結一下：

本文主要講述了為什麼要學習演算法，也簡單減少了數據結構與演算法之間的關系，隨後主要介紹了演算法中的入門知識：時間復雜度和空間復雜度。想要學好演算法，必須要掌握如何分析一個演算法的時間復雜度和空間復雜度，只有自己會分析這兩個個衡量演算法主要性能的標准，才能更好的寫出性能優秀的演算法，同時我們也講到了最好時間復雜度，最壞時間復雜度，平均時間復雜度和均攤時間復雜度，不過這四種復雜度的計算方式大家作為了解即可，等實際確實需要使用到再來回顧也不遲。

❻ 衡量演算法效率的方法與准則

演算法效率與分析
數據結構作為程序設計的基礎，其對演算法效率的影響必然是不可忽視的。本文就如何合理選擇數據結構來優化演算法這一問題，對選擇數據結構的原則和方法進行了一些探討。首先對數據邏輯結構的重要性進行了分析，提出了選擇邏輯結構的兩個基本原則；接著又比較了順序和鏈式兩種存儲結構的優點和缺點，並討論了選擇數據存儲結構的方法；最後本文從選擇數據結構的的另一角度出發，進一步探討了如何將多種數據結構進行結合的方法。在討論方法的同時，本文還結合實際，選用了一些較具有代表性的信息學競賽試題舉例進行了分析
【正文】一、引論
「數據結構＋演算法＝程序」，這就說明程序設計的實質就是對確定的問題選擇一種合適的數據結構，加上設計一種好的演算法。由此可見，數據結構在程序設計中有著十分重要的地位。
數據結構是相互之間存在一種或多種特定關系的數據元素的集合。因為這其中的「關系」，指的是數據元素之間的邏輯關系，因此數據結構又稱為數據的邏輯結構。而相對於邏輯結構這個比較抽象的概念，我們將數據結構在計算機中的表示又稱為數據的存儲結構。
建立問題的數學模型，進而設計問題的演算法，直至編出程序並進行調試通過，這就是我們解決信息學問題的一般步驟。我們要建立問題的數學模型，必須首先找出問題中各對象之間的關系，也就是確定所使用的邏輯結構；同時，設計演算法和程序實現的過程，必須確定如何實現對各個對象的操作，而操作的方法是決定於數據所採用的存儲結構的。因此，數據邏輯結構和存儲結構的好壞，將直接影響到程序的效率。

二、選擇合理的邏輯結構

在程序設計中，邏輯結構的選用就是要分析題目中的數據元素之間的關系，並根據這些特定關系來選用合適的邏輯結構以實現對問題的數學描述，進一步解決問題。邏輯結構實際上是用數學的方法來描述問題中所涉及的操作對象及對象之間的關系，將操作對象抽象為數學元素，將對象之間的復雜關系用數學語言描述出來。
根據數據元素之間關系的不同特性，通常有以下四種基本邏輯結構：集合、線性結構、樹形結構、圖狀（網狀）結構。這四種結構中，除了集合中的數據元素之間只有「同屬於一個集合」的關系外，其它三種結構數據元素之間分別為「一對一」、「一對多」、「多對多」的關系。
因此，在選擇邏輯結構之前，我們應首先把題目中的操作對象和對象之間的關系分析清楚，然後再根據這些關系的特點來合理的選用邏輯結構。尤其是在某些復雜的問題中，數據之間的關系相當復雜，且選用不同邏輯結構都可以解決這一問題，但選用不同邏輯結構實現的演算法效率大不一樣。
對於這一類問題，我們應採用怎樣的標准對邏輯結構進行選擇呢？
下文將探討選擇合理邏輯結構應充分考慮的兩個因素。

一、 充分利用「可直接使用」的信息。
首先，我們這里所講的「信息」，指的是元素與元素之間的關系。
對於待處理的信息，大致可分為「可直接使用」和「不可直接使用」兩類。對於「可直接使用」的信息，我們使用時十分方便，只需直接拿來就可以了。而對於「不可直接使用」的這一類，我們也可以通過某些間接的方式，使之成為可以使用的信息，但其中轉化的過程顯然是比較浪費時間的。
由此可見，我們所需要的是盡量多的「可直接使用」的信息。這樣的信息越多，演算法的效率就會越高。
對於不同的邏輯結構，其包含的信息是不同的，演算法對信息的利用也會出現不同的復雜程度。因此，要使演算法能夠充分利用「可直接使用」的信息，而避免演算法在信息由「不可直接使用」向「可直接使用」的轉化過程中浪費過多的時間，我們必然需要採用一種合理的邏輯結構，使其包含更多「可直接使用」的信息。
〖問題一〗 IOI99的《隱藏的碼字》。
〖問題描述〗
問題中給出了一些碼字和一個文本，要求編程找出文本中包含這些碼字的所有項目，並將找出的項目組成一個最優的「答案」，使得答案中各項目所包含的碼字長度總和最大。每一個項目包括一個碼字，以及該碼字在文本中的一個覆蓋序列（如』abcadc』就是碼字』abac』的一個覆蓋序列），並且覆蓋序列的長度不超過1000。同時，「答案」要求其中每個項目的覆蓋序列互相沒有重疊。
〖問題分析〗
對於此題，一種較容易得出的基本演算法是：對覆蓋序列在文本中的終止位置進行循環，再判斷包含了哪些碼字，找出所有項目，並最後使用動態規劃的方法將項目組成最優的「答案」。
演算法的其它方面我們暫且不做考慮，而先對問題所採用的邏輯結構進行選擇。
如果我們採用線性的邏輯結構（如循環隊列），那麼我們在判斷是否包含某個碼字t時，所用的方法為：初始時用指針p指向終止位置，接著通過p的不斷前移，依次找出碼字t從尾到頭的各個字母。例如碼字為「ABDCAB」，而文本圖1-1，終止位置為最右邊的箭頭符號，每個箭頭代表依次找到的碼字的各個字母。
指針p的移動方向
A B D C A B

C D A C B D C A D C D B A D C C B A D

圖1-1

由於題目規定碼字的覆蓋序列長度不超過1000，所以進行這樣的一次是否包含的判斷，其復雜度為O(1000)。
由於碼字t中相鄰兩字母在文本中的位置，並非只有相鄰(如圖1-1中的』D』和』C』)這一種關系，中間還可能間隔了許多的字母(如圖1-1中』C』和』A』就間隔了2個字母)，而線性結構中擁有的信息，僅僅只存在於相鄰的兩元素之間。通過這樣簡單的信息來尋找碼字的某一個字母，其效率顯然不高。
如果我們建立一個有向圖，其中頂點i(即文本的第i位)用52條弧分別連接』a』..』z』,』A』..』Z』這52個字母在i位以前最後出現的位置（如圖1-2的連接方式），我們要尋找碼字中某個字母的前一個字母，就可以直接利用已連接的邊，而不需用枚舉的方法。我們也可以把問題看為：從有向圖的一個頂點出發，尋找一條長度為length(t)-1的路徑，並且路徑中經過的頂點，按照碼字t中的字母有序。

C D A C B D C A D C D B A D C C B A D

圖1-2
通過計算，用圖進行記錄在空間上完全可以承受(記錄1000個點×52條弧×4位元組的長整型=200k左右)。在時間上，由於可以充分利用第i位和第i+1位弧的連接方式變化不大這一點(如圖1-2所示，第i位和第i+1位只有一條弧的指向發生了變化，即第i+1位將其中一條弧指向了第i位)，所以要對圖中的弧進行記錄，只需對弧的指向進行整體賦值，並改變其中的某一條弧即可。
因此，我們通過採用圖的邏輯結構，使得尋找字母的效率大大提高，其判斷的復雜度為O(length(t))，最壞為O(100)，比原來方法的判斷效率提高了10倍。
（附程序codes.pas）

對於這個例子，雖然用線性的數據結構也可以解決，但由於判斷的特殊性，每次需要的信息並不能從相鄰的元素中找到，而線性結構中只有相鄰元素之間存在關系的這一點，就成為了一個很明顯的缺點。因此，問題一線性結構中的信息，就屬於「不可直接使用」的信息。相對而言，圖的結構就正好滿足了我們的需要，將所有可能產生關系的點都用弧連接起來，使我們可以利用弧的關系，高效地進行判斷尋找的過程。雖然圖的結構更加復雜，但卻將「不可直接使用」的信息，轉化成為了「可直接使用」的信息，演算法效率的提高，自然在情理之中。。
二、 不記錄「無用」信息。
從問題一中我們看到，由於圖結構的信息量大，所以其中的信息基本上都是「可用」的。但是，這並不表示我們就一定要使用圖的結構。在某些情況下，圖結構中的「可用」信息，是有些多餘的。
信息都「可用」自然是好事，但倘若其中「無用」（不需要）的信息太多，就只會增加我們思考分析和處理問題時的復雜程度，反而不利於我們解決問題了。
〖問題二〗 湖南省1997年組隊賽的《乘船問題》
〖問題描述〗
有N個人需要乘船，而每船最多隻能載兩人，且必須同名或同姓。求最少需要多少條船。
〖問題分析〗
看到這道題，很多人都會想到圖的數據結構：將N個人看作無向圖的N個點，凡同名或同姓的人之間都連上邊。
要滿足用船最少的條件，就是需要盡量多的兩人共乘一條船，表現在圖中就是要用最少的邊完成對所有頂點的覆蓋。這就正好對應了圖論的典型問題：求最小邊的覆蓋。所用的演算法為「求任意圖最大匹配」的演算法。
使用「求任意圖最大匹配」的演算法比較復雜(要用到擴展交錯樹，對花的收縮等等)，效率也不是很高。因此，我們必須尋找一個更簡單高效的方法。
首先，由於圖中任兩個連通分量都是相對獨立的，也就是說任一條匹配邊的兩頂點，都只屬於同一個連通分量。因此，我們可以對每個連通分量分別進行處理，而不會影響最終的結果。
同時，我們還可以對需要船隻s的下限進行估計：
對於一個包含Pi個頂點的連通分量，其最小覆蓋邊數顯然為[Pi/2]。若圖中共有L個連通分量，則s=∑[Pi/2](1<=i<=L)。
然後，我們通過多次嘗試，可得出一個猜想：
實際需要的覆蓋邊數完全等於我們求出的下限∑[Pi/2](1<=i<=L)。
要用圖的結構對上述猜想進行證明，可參照以下兩步進行：
1． 連通分量中若不存在度為1的點，就必然存在迴路。
2． 從圖中刪去度為1的點及其相鄰的點，或刪去迴路中的任何一邊，連通分量依然連通，即連通分量必然存在非橋邊。
由於圖的方法不是這里的重點，所以具體證明不做詳述。而由採用圖的數據結構得出的演算法為：每次輸出一條非橋的邊，並從圖中將邊的兩頂點刪去。此演算法的時間復雜度為O(n3)。（尋找一條非橋邊的復雜度為O(n2)，尋找覆蓋邊操作的復雜度為O(n)）
由於受到圖結構的限制，時間復雜度已經無法降低，所以如果我們要繼續對演算法進行優化，只有考慮使用另一種邏輯結構。這里，我想到了使用二叉樹的結構，具體說就是將圖中的連通分量都轉化為二叉樹，用二叉樹來解決問題。
首先，我們以連通分量中任一個頂點作為樹根，然後我們來確定建樹的方法。
1． 找出與根結點i同姓的點j（j不在二叉樹中）作為i的左兒子，再以j為樹根建立子樹。
2． 找出與根結點i同名的點k（k不在二叉樹中）作為i的右兒子，再以k為樹根建立子樹。
如圖2-1-1中的連通分量，我們通過上面的建樹方法，可以使其成為圖2-1-2中的二叉樹的結構(以結點1為根)。（兩點間用實線表示同姓，虛線表示同名）

圖2-1-2

圖2-1-1
接著，我就來證明這棵樹一定包含了連通分量中的所有頂點。
【引理2.1】
若二叉樹T中包含了某個結點p，那麼連通分量中所有與p同姓的點一定都在T中。
證明：
為了論證的方便，我們約定：s表示與p同姓的頂點集合；lc[p,0]表示結點p，lc[p,i](i>0)表示lc[p,i-1]的左兒子，顯然lc[p,i]與p是同姓的。
假設存在某個點q，滿足qs且qT。由於s是有限集合，因而必然存在某個lc[p,k]無左兒子。則我們可以令lc[p,k+1]=q，所以qT，與假設qT相矛盾。
所以假設不成立，原命題得證。

由引理2.1的證明方法，我們同理可證引理2.2。
【引理2.2】
若二叉樹T中包含了某個結點p，那麼連通分量中所有與p同名的點一定都在T中。

有了上面的兩個引理，我們就不難得出下面的定理了。
【定理一】
以連通分量中的任一點p作為根結點的二叉樹，必然能夠包含連通分量中的所有頂點。
證明：
由引理2.1和引理2.2，所有與p同姓或同名的點都一定在二叉樹中，即連通分量中所有與p有邊相連的點都在二叉樹中。由連通分量中任兩點間都存在路徑的特性，該連通分量中的所有點都在二叉樹中。

在證明二叉樹中包含了連通分量的所有頂點後，我們接著就需要證明我們的猜想，也就是下面的定理：
【定理二】包含m個結點的二叉樹Tm，只需要船的數量為boat[m]=[m/2](mN)。
證明：
(i) 當m=1,m=2,m=3時命題顯然成立。

圖2-2-1

圖2-2-2

圖2-2-3
(ii) 假設當m<k(k>3)時命題成立，那麼當m=k時，我們首先從樹中找到一個層次最深的結點，並假設這個結點的父親為p。那麼，此時有且只有以下三種情況（結點中帶有陰影的是p結點）：
(1) 如圖2-2-1，p只有一個兒子。此時刪去p和p唯一的兒子，Tk就成為了Tk-2，則boat[k]=boat[k-2]+1=[(k-2)/2]+1=[k/2]。
(2) 如圖2-2-2，p有兩個兒子，並且p是其父親的左兒子。此時可刪去p和p的右兒子，並可將p的左兒子放到p的位置上。同樣地，Tk成為了Tk-2，boat[k]=boat[k-2]+1=[k/2]。
(3) 如圖2-2-3，p有兩個兒子，並且p是其父親的右兒子。此時可刪去p和p的左兒子，並可將p的右兒子放到p的位置上。情況與(2)十分相似，易得此時得boat[k]=boat[k-2]+1=[k/2]。
綜合(1)、(2)、(3)，當m=k時，boat[k]=[k/2]。
最後，綜合(i)、(ii)，對於一切mN，boat[m]=[m/2]。

由上述證明，我們將問題中數據的圖結構轉化為樹結構後，可以得出求一棵二叉樹的乘船方案的演算法：
proc try(father:integer;var root:integer;var rest:byte);
{輸出root為樹根的子樹的乘船方案，father=0表示root是其父親的左兒子，
father=1表示root是其父親的右兒子，rest表示輸出子樹的乘船方案後，
是否還剩下一個根結點未乘船}
begin
visit[root]:=true; {標記root已訪問}
找到一個與root同姓且未訪問的結點j;
if j<>n+1 then try(0,j,lrest);
找到一個與root同姓且未訪問的結點k;
if k<>n+1 then try(1,k,rrest);
if (lrest=1) xor (rrest=1) then begin {判斷root是否只有一個兒子，情況一}
if lrest=1 then print(lrest,root) else print(rrest,root);
rest:=0;
end
else if (lrest=1) and (rrest=1) then begin {判斷root是否有兩個兒子}
if father=0 then begin
print(rrest,root);root:=j; {情況二}
end
else begin
print(lrest,root);root:=k; {情況三}
end;
rest:=1;
end
else rest:=1;
end;

這只是輸出一棵二叉樹的乘船方案的演算法，要輸出所有人的乘船方案，我們還需再加一層循環，用於尋找各棵二叉樹的根結點，但由於每個點都只會訪問一次，尋找其左右兒子各需進行一次循環，所以演算法的時間復雜度為O(n2)。（附程序boat.pas）

最後，我們對兩種結構得出不同時間復雜度演算法的原因進行分析。其中最關鍵的一點就是因為二叉樹雖然結構相對較簡單，但已經包含了幾乎全部都「有用」的信息。由我們尋找乘船方案的演算法可知，二叉樹中的所有邊不僅都發揮了作用，而且沒有重復的使用，可見信息的利用率也是相當之高的。
既然採用樹結構已經足夠，圖結構中的一些信息就顯然就成為了「無用」的信息。這些多餘的「無用」信息，使我們在分析問題時難於發現規律，也很難找到高效的演算法進行解決。這正如迷宮中的牆一樣，越多越難走。「無用」的信息，只會干擾問題的規律性，使我們更難找出解決問題的方法。

小結
我們對數據的邏輯結構進行選擇，是構造數學模型一大關鍵，而演算法又是用來解決數學模型的。要使演算法效率高，首先必須選好數據的邏輯結構。上面已經提出了選擇邏輯結構的兩個條件（思考方向），總之目的是提高信息的利用效果。利用「可直接使用」的信息，由於中間不需其它操作，利用的效率自然很高；不不記錄「無用」的信息，就會使我們更加專心地研究分析「有用」的信息，對信息的使用也必然會更加優化。
總之，在解決問題的過程中，選擇合理的邏輯結構是相當重要的環
三、 選擇合理的存儲結構
數據的存儲結構，分為順序存儲結構和鏈式存儲結構。順序存儲結構的特點是藉助元素在存儲器中的相對位置來表示數據元素之間的邏輯關系；鏈式存儲結構則是藉助指示元素存儲地址的指針表示數據元素之間的邏輯關系。
因為兩種存儲結構的不同，導致這兩種存儲結構在具體使用時也分別存在著優點和缺點。
這里有一個較簡單的例子：我們需要記錄一個n×n的矩陣，矩陣中包含的非0元素為m個。
此時，我們若採用順序存儲結構，就會使用一個n×n的二維數組，將所有數據元素全部記錄下來；若採用鏈式存儲結構，則需要使用一個包含m個結點的鏈表，記錄所有非0的m個數據元素。由這樣兩種不同的記錄方式，我們可以通過對數據的不同操作來分析它們的優點和缺點。
1． 隨機訪問矩陣中任意元素。由於順序結構在物理位置上是相鄰的，所以可以很容易地獲得任意元素的存儲地址，其復雜度為O(1)；對於鏈式結構，由於不具備物理位置相鄰的特點，所以首先必須對整個鏈表進行一次遍歷，尋找需進行訪問的元素的存儲地址，其復雜度為O(m)。此時使用順序結構顯然效率更高。
2． 對所有數據進行遍歷。兩種存儲結構對於這種操作的復雜度是顯而易見的，順序結構的復雜度為O(n2)，鏈式結構為O(m)。由於在一般情況下m要遠小於n2，所以此時鏈式結構的效率要高上許多。
除上述兩種操作外，對於其它的操作，這兩種結構都不存在很明顯的優點和缺點，如對鏈表進行刪除或插入操作，在順序結構中可表示為改變相應位置的數據元素。
既然兩種存儲結構對於不同的操作，其效率存在較大的差異，那麼我們在確定存儲結構時，必須仔細分析演算法中操作的需要，合理地選擇一種能夠「揚長避短」的存儲結構。

一、合理採用順序存儲結構。
我們在平常做題時，大多都是使用順序存儲結構對數據進行存儲。究其原因，一方面是出於順序結構操作方便的考慮，另一方面是在程序實現的過程中，使用順序結構相對於鏈式結構更便於對程序進行調試和查找錯誤。因此，大多數人習慣上認為，能夠使用順序結構進行存儲的問題，最「好」採用順序存儲結構。
其實，這個所謂的「好」只是一個相對的標准，是建立在以下兩個前提條件之下的：
1． 鏈式結構存儲的結點與順序結構存儲的結點數目相差不大。這種情況下，由於存儲的結點數目比較接近，使用鏈式結構完全不能體現出記錄結點少的優點，並且可能會由於指針操作較慢而降低演算法的效率。更有甚者，由於指針自身佔用的空間較大，且結點數目較多，因而演算法對空間的要求可能根本無法得到滿足。
2． 並非演算法效率的瓶頸所在。由於不是演算法最費時間的地方，這里是否進行改進，顯然是不會對整個演算法構成太大影響的，若使用鏈式結構反而會顯得操作過於繁瑣。

二、必要時採用鏈式存儲結構。
上面我對使用順序存儲結構的條件進行了分析，最後就只剩下何時應該採用鏈式存儲結構的問題了。
由於鏈式結構中指針操作確實較繁瑣，並且速度也較慢，調試也不方便，因而大家一般都不太願意用鏈式的存儲結構。但是，這只是一般的觀點，當鏈式結構確實對演算法有很大改進時，我們還是不得不進行考慮的。
〖問題三〗 IOI99的《地下城市》。
〖問題描述〗
已知一個城市的地圖，但未給出你的初始位置。你需要通過一系列的移動和探索，以確定初始時所在的位置。題目的限制是：
1． 不能移動到有牆的方格。
2． 只能探索當前所在位置四個方向上的相鄰方格。
在這兩個限制條件下，要求我們的探索次數（不包括移動）盡可能的少。
〖問題分析〗
由於存儲結構要由演算法的需要確定，因此我們首先來確定問題的演算法。
經過對問題的分析，我們得出解題的基本思想：先假設所有無牆的方格都可能是初始位置，再通過探索一步步地縮小初始位置的范圍，最終得到真正的初始位置。同時，為提高演算法效率，我們還用到了分治的思想，使我們每一次探索都盡量多的縮小初始位置的范圍(使程序盡量減少對運氣的依賴)。
接著，我們來確定此題的存儲結構。
由於這道題的地圖是一個二維的矩陣，所以一般來講，採用順序存儲結構理所當然。但是，順序存儲結構在這道題中暴露了很大的缺點。我們所進行的最多的操作，一是對初始位置的范圍進行篩選，二是判斷要選擇哪個位置進行探索。而這兩種操作，所需要用到的數據，只是龐大地圖中很少的一部分。如果採用順序存儲結構(如圖3-1中陰影部分表示已標記)，無論你需要用到多少數據，始終都要完全的遍歷整個地圖。

4
3
2
1
1 2 3 4
圖3-1

head

圖3-2
然而，如果我們採用的是鏈式存儲結構(如圖3-2的鏈表)，那麼我們需要多少數據，就只會遍歷多少數據，這樣不僅充分發揮了鏈式存儲結構的優點，而且由於不需單獨對某一個數據進行提取，每次都是對所有數據進行判斷，從而避免了鏈式結構的最大缺點。
我們使用鏈式存儲結構，雖然沒有降低問題的時間復雜度(鏈式存儲結構在最壞情況下的存儲量與順序存儲結構的存儲量幾乎相同)，但由於體現了前文所述選擇存儲結構時揚長避短的原則，因而演算法的效率也大為提高。（程序對不同數據的運行時間見表3-3）
測試數據編號 使用順序存儲結構的程序 使用鏈式存儲結構的程序
1 0.06s 0.02s
2 1.73s 0.07s
3 1.14s 0.06s
4 3.86s 0.14s
5 32.84s 0.21s
6 141.16s 0.23s
7 0.91s 0.12s
8 6.92s 0.29s
9 6.10s 0.23s
10 17.41s 0.20s

表3-3
（附使用鏈式存儲結構的程序under.pas）
我們選擇鏈式的存儲結構，雖然操作上可能稍復雜一些，但由於改進了演算法的瓶頸，演算法的效率自然也今非昔比。由此可見，必要時選擇鏈式結構這一方法，其效果是不容忽視的。
小結
合理選擇邏輯結構，由於牽涉建立數學模型的問題，可能大家都會比較注意。但是對存儲結構的選擇，由於不會對演算法復雜度構成影響，所以比較容易忽視。那麼，這種不能降低演算法復雜度的方法是否需要重視呢？
大家都知道，剪枝作為一種常用的優化演算法的方法，被廣泛地使用，但剪枝同樣是無法改變演算法的復雜度的。因此，作用與剪枝相似的存儲結構的合理選擇，也是同樣很值得重視的。
總之，我們在設計演算法的過程中，必須充分考慮存儲結構所帶來的不同影響，選擇最合理的存儲結構。

四、 多種數據結構相結合

上文所探討的，都是如何對數據結構進行選擇，其中包含了邏輯結構的選擇和存儲結構的選擇，是一種具有較大普遍性的演算法優化方法。對於多數的問題，我們都可以通過選擇一種合理的邏輯結構和存儲結構以達到優化演算法的目的。
但是，有些問題卻往往不如人願，要對這類問題的數據結構進行選擇，常常會顧此失彼，有時甚至根本就不存在某一種合適的數據結構。此時，我們是無法選擇出某一種合適的數據結構的，以上的方法就有些不太適用了。
為解決數據結構難以選擇的問題，我們可以採用將多種數據結構進行結合的方法。通過多種數據結構相結合，達到取長補短的作用，使不同的數據結構在演算法中發揮出各自的優勢。
這只是我們將多種數據結構進行結合的總思想，具體如何進行結合，我們可以先看下面的例子。
我們可以採用映射的方法，將線性結構中的元素與堆中間的結點一一對應起來，若線性的數組中的元素發生變化，堆中相應的結點也接著變化，堆中的結點發生變化，數組中相應的元素也跟著變化。
將兩種結構進行結合後，無論是第一步還是第二步，我們都不需對所有元素進行遍歷，只需進行常數次復雜度為O(log2n)的堆化操作。這樣，整個時間復雜度就成為了O(nlog2n)，演算法效率無疑得到了很大提高。

五、 總結
我們平常使用數據結構，往往只將其作為建立模型和演算法實現的工具，而沒有考慮這種工具對程序效率所產生的影響。信息學問題隨著難度的不斷增大，對演算法時空效率的要求也越來越高，而演算法的時空效率，在很大程度上都受到了數據結構的制約。

❼ 演算法的時間和空間的概念

1.空間復雜度:
比如java中int是4個位元組,long是8個位元組,你可以用long表示一個數字,long a=100,同樣可以用int b=100;這樣我們用int肯定比long要節省空間,再者就是同樣讓許多人編寫一個C程序,其中用的變數的個數可能大不一樣,變數越多可能你的程序越容易讓別人看懂,但變數越少,程序可能看懂的人不多,不過現在都不再強調這復雜度,1G的內存多的是了,幾個位元組也不算什麼了,不過在硬體驅動開發的時候比較講究這個
2.時間復雜度:
這是一個相對的概念,比如我用p2的電腦和p4的同樣運行一個程序,你說哪個快?只能在一定的硬體環境下談時間復雜度
;所以程序步的方式來說時間復雜度比較方便
打個比方:
for(int i=0;i<100;i++)
{
sum=sum+i;
}
sum=sum+i;這條語句執行了100次,就說這條語句的程序步是
100;像注釋,聲明語句的程序步都為0;