數據結構——算法和算法效率的度量

一、引言

二、算法

1 算法的基本概念

?2 算法的復雜度

2.1 時間復雜度

2.1.1 概念

2.1.2 大O的漸進表示

3 算法的空間復雜度

3.1 概念

?3.2 實例

4 實例分析

5 結論

一、引言

大家在寫代碼的時候有沒有發現寫同樣功能的代碼有多種不同的寫法，而不同的代碼也會給我們的程序帶去不同的影響，比如有的代碼執行的快，有的代碼執行的慢；有的代碼申請的空間大，有的代碼申請的空間小，那這是為什么呢？因為是算法不同呀，那為什么不同呢，接下來就由姜糖給大家講講算法這一特殊的名詞。

二、算法

1 算法的基本概念

算法(Algorithm)是對特定問題求解步驟的一種描述，它是指令的有限序列，其中的每條指令表示一個或多個操作。此外，一個算法還具有下列五個重要特性：

有窮性。一個算法必須總在執行有窮步之后結束，且每一步都可在有窮時間內完成。
確定性。算法中每條指令必須有確切的含義，對于相同的輸入只能得出相同的輸出。
可行性。算法中描述的操作都可以通過已經實現的基本運算執行有限次來實現。
輸入。一個算法有零個或多個輸入，這些輸入取自于某個特定的對象的集合。
輸出。一個算法有一個或多個輸出，這些輸出是與輸入有著某種特定關系的量。

通常，設計一個“好”的算法應考慮達到以下目標：

正確性。算法應能夠正確地解決求解問題。
可讀性。算法應具有良好的可讀性，以幫助人們理解。
健壯性。算法能對輸入的非法數據做出反應或處理，而不會產生莫名其妙的輸出。
高效率與低存儲量需求。效率是指算法執行的時間，存儲量需求是指算法執行過程中所需要的最大存儲空間，這兩者都與問題的規模有關。

?2 算法的復雜度

算法效率的度量是通過時間復雜度和空間復雜度來描述的。

2.1 時間復雜度

說起時間可能有的人就會說，運行時間嘛我也會，把代碼放在電腦上面跑一下就知道了。那大家想過沒，我拿學校機房大LOL都卡的電腦和家里豪華rog全家桶來跑一個代碼，他們的運行時間會一樣嗎？那有的人可能會說那放在同一臺電腦上跑不就行了嗎？那萬一網卡了呢，時間不就又不一樣了。所以算法中就有一個時間復雜度的概念。

2.1.1 概念

時間復雜度的定義：在計算機科學中，算法的時間復雜度是一個函數，它定量描述了該算法的運行時間。一個算法執行所耗費的時間，從理論上說，是不能算出來的，只有你把你的程序放在機器上跑起來，才能知道。但是我們需要每個算法都上機測試嗎？是可以都上機測試，但是這很麻煩，所以才有了時間復雜度這個分析方式。一個算法所花費的時間與其中語句的執行次數成正比例，算法中的基本操作的執行次數，為算法的時間復雜度。

?那接下來我們來看一個程序來找出他的執行次數：

void Func1(int n)
{int count = 0;for(int i = 0; i < n ; i++){for(int j = 0 ;j < n ; j++){    count++;}}for(int k = 0; k<2*n ; k++){count++;}int m = 10;while(m--){count:}printf("%d\n",count);
}

次數：

$F(N)=N^{2}+2*N+10$

當我們發現當N足夠大時，2*N+10對函數的影響可以忽略不記，所以 $F(N)=N^{2}$ ?。

所有我們計算時間復雜度的時候，我們其實并不一定有計算精確的次數，只需要一個大概就好了，所有我們這里可以用大O的漸進表示法。

2.1.2 大O的漸進表示

?大O符號：是用于描述函數漸進行為的數學符號。

推導大O階的方法：

用常數1取代運行時間中的所有加法常數。
在修改后的運行次數函數中，只保留高階項。
如果最高階項存在且不是1，且去除于這個項目相乘的常數。得到的結果就是大O階。

所以上面例子代碼的時間復雜度為：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? $O(N^{2})$

*時間復雜度中，變量一般用N表示。

接下來再舉一個讓我們對大O階漸進表示有更深一步的認識：

void Func2(int n)
{int count = 0;for(int k = 0; k<2*n ; k++){count++;}int m = 10;while(m--){count:}printf("%d\n",count);
}

?那么這個函數的時間復雜度為什么呢？

F(N)=2N+10，只保留最高項，然后去掉最高項的常數，所以最后為O（N）。

在大O漸進表示中有一些特殊的：

比如有兩個變量N和M，在沒有特殊說明N或者M遠遠大于另外一個時：O(N+M);
O(常數)時用O(1)表示

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

const char strchr( const char* str, int character)
{while(*str){if(*str==character)return str;++str;}
}

這是一個在字符串中查找的函數

他的次數不固定，最好的情況為?O(1)，最壞的情況是O(n)，平均情況是O(n/2)。那我們該選擇哪種情況呢？

這算法中我們一般選擇最壞的運行情況，以保證算法的運行時間不會比它更長。

就如同我們生活中約會一樣，我們到達的時間不可能比對象晚，不然后果很嚴重，所以我們要把最壞的時間告訴她，給我們留下充足的時間赴約。

3 算法的空間復雜度

3.1 概念

空間復雜度：也是一個數學表達式，是對一個算法在運行過程中臨時占用存儲空間大小的量度。空間復雜度不是程序占用了多少bytes的空間，因為這個也沒太大意義，所以空間復雜度算的是變量的個數。空間復雜度計算規則基本跟實踐復雜度類似，也使用大O漸進表示法。注意：函數運行時所需要的棧空間(存儲參數、局部變量、一些寄存器信息等)在編譯期間已經確定好了，因此空間復雜度主要通過函數在運行時候顯式申請的額外空間來確定。

?3.2 實例

下面我們來看代碼進行分析：

// 計算階乘遞歸Fac的空間復雜度？
long long Fac(size_t N)
{if(N == 0)return 1;return Fac(N-1)*N;
}

該函數為階乘遞歸，自身的遞歸每進行一次都會重新創造一個變量N,如圖：

所以該函數創造的變量為N+1，用大O漸進法空間復雜度為O(N)。

4 實例分析

我們現在學習了空間復雜度和時間復雜度，那接下來我們用一道題結束今天的文章：

斐波那契數列（遞歸方法）：

#include<stdio.h>int Fibonacci(int N)
{if (N < 3){return 1;}elsereturn Fibonacci(N - 1) + Fibonacci(N - 2);
}int main()
{printf("%d", Fibonacci(10));return 0;
}

大家想想它的時間和空間復雜度為多少呢？

在分析之前我想告訴大家的是，做這類題的時候我們畫圖是很有利于我們理解的，如圖：

根據話題我們可以輕而易舉的知道函數時間復雜度的大O為 $O(2^{N})$ （綠色部分缺少為常數所以忽略不計）

而時間復雜度呢，可能有人覺得也是 $O(2^{N})$ ,答案卻是錯誤的。那這是為什么呢？

那是因為函數是按照順序執行的，如圖函數肯定是先執行1然后執行完銷毀完內存后才會執行2，

?而空間內存算的是函數執行需要的空間，當部分函數執行完的時候，空間就會被銷毀，后續的函數會重新利用這一部分被銷毀的空間，所以我們在這里算空間復雜度的時候，又該選擇執行最大的一條如圖藍色部分，則最大申請變量為N+1，用大O漸進法表示則為：O(N)。

*大家注意

時間的消逝是回不來了的

空間是一直在的，是可以重復利用的

5 結論

姜糖最近因為特殊情況正逐步向著數據結構的方向前進，如有不足請大佬們幫我指出，姜糖也會不斷去更新自己博客，不斷反思完善自我，與各位一起邁入大牛之列。希望大家能一鍵三連，謝謝大家！

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/bicheng/22066.shtml
繁體地址，請注明出處：http://hk.pswp.cn/bicheng/22066.shtml
英文地址，請注明出處：http://en.pswp.cn/bicheng/22066.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！