??個(gè)人主頁：聆風(fēng)吟
??系列專欄：圖解數(shù)據(jù)結(jié)構(gòu)、算法模板
??少年有夢(mèng)不應(yīng)止于心動(dòng)，更要付諸行動(dòng)。

一. ??算法的定義

????算法是解決特定問題求解步驟的描述，在計(jì)算機(jī)中表現(xiàn)為指令的有限序列，并且每條指令表示一個(gè)或多個(gè)操作。

二. ??算法的特性

????算法具有五個(gè)基本特性：輸入、輸出、有窮性、確定性和可行性。

2.1 ??輸入輸出

????算法具有零個(gè)或多個(gè)輸入，盡管對(duì)于大多數(shù)算法來說，輸入?yún)?shù)都是有必要的，但對(duì)于個(gè)別情況，如打印"hello world!"這樣的代碼，不需要任何輸入?yún)?shù)，因此算法的輸入可以是零個(gè)。

2.2 ??輸入輸出

????算法至少有一個(gè)或多個(gè)輸出，算法是一定需要輸出的，不需要輸出，你用這個(gè)算法干嘛呢？輸出的形式可以打印輸出，也可以是返回一個(gè)或多個(gè)值等。

2.3 ??有窮性

????有窮性：是指算法在執(zhí)行有限的步驟之后，自動(dòng)結(jié)束而不會(huì)出現(xiàn)無限循環(huán)，并且每一個(gè)步驟都在可接受的時(shí)間內(nèi)完成。

2.4 ??確定性

????確定性：算法的每一步驟都具有確定的含義，不會(huì)出現(xiàn)二義性。算法在一定條件下，只有一條執(zhí)行的路徑，相同的輸入只能有唯一的輸出結(jié)果。算法的每一步驟都被精確定義而無歧義。

2.5 ??可行性

????可行性：算法的每一步都必須是可行的，也就是說，每一步都能夠通過執(zhí)行有限次數(shù)完成。

三. ??算法設(shè)計(jì)要求

????算法不是唯一的。也就是說，解決同一個(gè)問題，可以有多種解決問題的算法。通常為了設(shè)計(jì)一個(gè) “好” 的算法應(yīng)考慮達(dá)到一下目標(biāo)：

3.1 ??正確性

????正確性：算法的正確性是指算法至少應(yīng)該具有輸入、輸出和加工處理無歧義性，能夠得到問題的正確答案。但是算法的 “ 正確 ” 一詞在用法上通常有很大差別，大體分為一下四個(gè)層次：

1. 算法程序沒有語法錯(cuò)誤；
2. 算法程序?qū)τ诤戏ǖ妮斎霐?shù)據(jù)能夠產(chǎn)生滿足要求的輸入結(jié)果；
3. 算法程序?qū)τ诜欠ǖ妮斎霐?shù)據(jù)能夠得出滿足規(guī)格說明的結(jié)果；
4. 算法程序?qū)τ诰倪x擇的，甚至刁難的測(cè)試數(shù)據(jù)都有滿足要求的輸出結(jié)果。

對(duì)于這四層含義，層次 1的要求最低，但僅僅沒有語法錯(cuò)誤實(shí)在談不上是好算法。這就是如同僅僅解決溫飽，不算是生活幸福一樣。而層次 4是最難實(shí)現(xiàn)的，我們幾乎不可能逐一驗(yàn)證所有的輸入都得到正確的結(jié)果。所以一般情況下，我們通常把層次 3作為衡量一個(gè)算法算法是否合格的標(biāo)準(zhǔn)。

3.2 ??可讀性

????可讀性：算法的另一個(gè)目的是為了便于閱讀，來理解和交流?？勺x性高有助于人們理解算法，晦澀難懂的算法往往隱含錯(cuò)誤，不易被發(fā)現(xiàn)，并且難以調(diào)試和修改。

3.2 ??健壯性

????健壯性：當(dāng)輸入數(shù)據(jù)不合法時(shí)，算法也能做出相關(guān)處理而不是產(chǎn)生異常或莫名其妙的結(jié)果。

3.3 ??時(shí)間效率高和存儲(chǔ)量低

????時(shí)間效率指的是算法的執(zhí)行時(shí)間。對(duì)于同一個(gè)問題，如果有多個(gè)算法能夠解決，執(zhí)行時(shí)間短的算法效率高，執(zhí)行時(shí)間長的效率低。存儲(chǔ)量需求指的是算法在執(zhí)行過程中需要的最大空間，主要指算法程序運(yùn)行時(shí)所占用的內(nèi)存或外部硬盤存儲(chǔ)空間。因此，設(shè)計(jì)算法時(shí)應(yīng)盡量滿足時(shí)間效率高和存儲(chǔ)量低的需求。

四. ??算法效率的度量方法

????剛才我們提到了設(shè)計(jì)算法要提高效率。這里的效率大都指算法的執(zhí)行時(shí)間。算法的執(zhí)行時(shí)間需要依據(jù)該算法編制的程序在計(jì)算機(jī)上運(yùn)行時(shí)所消耗的時(shí)間來度量的。而度量一個(gè)程序的執(zhí)行時(shí)間通常有有兩種方法 —— 事后統(tǒng)計(jì)方法和事前分析估算方法。

4.1 ??事后統(tǒng)計(jì)方法

????事后統(tǒng)計(jì)方法：這種方法主要是通過設(shè)計(jì)好的測(cè)試程序和數(shù)據(jù)，利用計(jì)算機(jī)計(jì)時(shí)器對(duì)不同的算法編制的程序的運(yùn)行時(shí)間進(jìn)行比較，從而確定算法效率的高低。但是這種方法明顯是有很大的缺陷：

• 必須要依據(jù)算法事先編制好程序，這通常要需要花費(fèi)大量時(shí)間和精力。如果編制出來發(fā)現(xiàn)它根本就是一團(tuán)很糟糕的算法，那不就是竹籃打水一場(chǎng)空了嗎？
• 時(shí)間的比較依賴計(jì)算機(jī)硬件和軟件等環(huán)境因素的影響，有時(shí)會(huì)掩蓋算法本身的優(yōu)劣。
• 算法的測(cè)試數(shù)據(jù)設(shè)計(jì)困難，并且程序的運(yùn)行時(shí)間往往還與測(cè)試數(shù)據(jù)的規(guī)模有很大關(guān)系，效率高的算法在小的測(cè)試數(shù)據(jù)面前往往得不到體現(xiàn)。

基于事后統(tǒng)計(jì)方法有這樣那樣的缺陷，我們一般不予以采納，而是采用另一種事前分析估算方法。

4.2 ??事前分析估算方法

????事前分析估算方法：在計(jì)算機(jī)程序編制前，依據(jù)統(tǒng)計(jì)方法對(duì)算法進(jìn)行估算。經(jīng)過分析我們可以發(fā)現(xiàn)，一個(gè)用高級(jí)語言程序語言編寫的程序在計(jì)算機(jī)上運(yùn)行時(shí)所消耗的時(shí)間取決于一下因素：
解析：
????第（1）條是一個(gè)好算法的根本，第（2）條要有軟件來支持，第（4）條要看硬件性能。因此，拋開這些與計(jì)算機(jī)硬件、軟件有關(guān)的因素，一個(gè)程序的運(yùn)行時(shí)間，依賴于算法的好壞和問題的輸入規(guī)模。所謂問題輸入規(guī)模是指輸入量的多少。

五. ??算法的復(fù)雜度

5.1 ??算法的復(fù)雜度的簡單介紹

????算法在編寫成可執(zhí)行程序后，運(yùn)行時(shí)需要耗費(fèi)時(shí)間資源和空間(內(nèi)存)資源 。因此衡量一個(gè)算法的好壞，一般是從時(shí)間和空間兩個(gè)維度來衡量的，即時(shí)間復(fù)雜度和空間復(fù)雜度。

????時(shí)間復(fù)雜度主要衡量一個(gè)算法的運(yùn)行快慢，而空間復(fù)雜度主要衡量一個(gè)算法運(yùn)行所需要的額外空間。在計(jì)算機(jī)發(fā)展的早期，計(jì)算機(jī)的存儲(chǔ)容量很小。所以對(duì)空間復(fù)雜度很是在乎。但是經(jīng)過計(jì)算機(jī)行業(yè)的迅速發(fā)展，計(jì)算機(jī)的存儲(chǔ)容量已經(jīng)達(dá)到了很高的程度。所以我們?nèi)缃褚呀?jīng)不需要再特別關(guān)注一個(gè)算法的空間復(fù)雜度。

5.2 ??算法復(fù)雜度在面試中考察

由此可以看出算法復(fù)雜度的重要性，所以說同學(xué)們下面的內(nèi)容一定要好好學(xué)哦。言歸正傳接下來讓我們開始具體講解時(shí)間復(fù)雜度和空間復(fù)雜度。

六. ??算法的時(shí)間復(fù)雜度（重點(diǎn)）

6.1 ??算法的時(shí)間復(fù)雜度定義

????在計(jì)算機(jī)科學(xué)中，算法的時(shí)間復(fù)雜度是一個(gè)函數(shù)，它定量描述了該算法的運(yùn)行時(shí)間。一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間，從理論上說，是不能算出來的，只有你把你的程序放在機(jī)器上跑起來，才能知道。但是我們需要每個(gè)算法都上機(jī)測(cè)試嗎？是可以都上機(jī)測(cè)試，但是這很麻煩，所以才有了時(shí)間復(fù)雜度這個(gè)分析方式。一個(gè)算法所花費(fèi)的時(shí)間與其中語句的執(zhí)行次數(shù)成正比例，算法中的基本操作的執(zhí)行次數(shù)，為算法的時(shí)間復(fù)雜度。
即：找到某條基本語句與問題規(guī)模N之間的數(shù)學(xué)表達(dá)式，就是算出了該算法的時(shí)間復(fù)雜度。

• 示例：請(qǐng)計(jì)算一下Func1中++count語句總共執(zhí)行了多少次？

void Func1(int N)
{
	int count = 0;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			++count;//執(zhí)行 N*N 次
		}
	}

	for (int k = 0; k < 2 * N; ++k)
	{
		++count;//執(zhí)行 2*N 次
	}

	int M = 10;
	while (M--)
	{
		++count;//執(zhí)行 10次
	}

	printf("%d\n", count);
}

???? 實(shí)際中我們計(jì)算時(shí)間復(fù)雜度時(shí)，我們其實(shí)并不一定要計(jì)算精確的執(zhí)行次數(shù)，而只需要大概執(zhí)行次數(shù)，那么我們就可以使用大O的漸進(jìn)表示法。看到這估計(jì)有同學(xué)該問了大O的漸進(jìn)表示法是什么，它又是如何推導(dǎo)的呢？且聽我慢慢道來，讓我們繼續(xù)接著向下面學(xué)習(xí)。

6.2 ??大O的漸進(jìn)表示法

大O符號(hào)（big O notation）：是用于于描述函數(shù)漸進(jìn)行為的數(shù)學(xué)符號(hào)。

推導(dǎo)大O階方法：

（1）用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)。
（2） 在修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高階項(xiàng)。
（3）如果最高階項(xiàng)存在且其系數(shù)不是1，則去除與這個(gè)項(xiàng)相乘的系數(shù)。得到的結(jié)果就是大O階。

結(jié)合上面示例： 使用大O的漸進(jìn)表示法以后，F(xiàn)unc1的時(shí)間復(fù)雜度為：

通過上面我們會(huì)發(fā)現(xiàn)大O的漸進(jìn)表示法去掉了那些對(duì)結(jié)果影響不大的項(xiàng)，簡潔明了的表示出了執(zhí)行次數(shù)。

6.3 ??常見的時(shí)間復(fù)雜度

??常見的時(shí)間復(fù)雜度如下表所示：
注：對(duì)數(shù)在文本中不好表示，以 2 為底的對(duì)數(shù)通常簡寫為(logn) 。

??常用的時(shí)間復(fù)雜度所耗費(fèi)的時(shí)間從小到大依次是：

O(1) < O(logn) < O(n) < O(nlogn) < O(2n) < O(n3) < O(2n) < O(n!)

6.4 ??最好情況、最壞情況與平均情況

另外有些算法的時(shí)間復(fù)雜度存在最好、平均和最壞情況：

• 最壞情況：任意輸入規(guī)模的最大運(yùn)行次數(shù)(上界)
• 平均情況：任意輸入規(guī)模的期望運(yùn)行次數(shù)
• 最好情況：任意輸入規(guī)模的最小運(yùn)行次數(shù)(下界)

例如：在一個(gè)長度為N數(shù)組中搜索一個(gè)數(shù)據(jù)x
??????最好情況：1次找到
??????最壞情況：N次找到
??????平均情況：N/2次找到
在實(shí)際中 一般在沒有特殊說明的情況下，關(guān)注的都是算法的最壞運(yùn)行情況，所以數(shù)組中搜索數(shù)據(jù)時(shí)間復(fù)雜度為O(N)。

七. ??算法的空間復(fù)雜度

算法空間復(fù)雜度的定義：

• 空間復(fù)雜度也是一個(gè)數(shù)學(xué)表達(dá)式，是對(duì)一個(gè)算法在運(yùn)行過程中額外臨時(shí)占用存儲(chǔ)空間大小的量度 。
• 空間復(fù)雜度不是程序占用了多少bytes的空間，因?yàn)檫@個(gè)也沒太大意義，所以 空間復(fù)雜度算的是變量的個(gè)數(shù)。
• 空間復(fù)雜度計(jì)算規(guī)則基本跟時(shí)間復(fù)雜度類似，也使用大O漸進(jìn)表示法。

注意： 函數(shù)運(yùn)行時(shí)所需要的棧空間（存儲(chǔ)參數(shù)、局部變量、一些寄存器信息等）在編譯期間已經(jīng)確定好了，因此空間復(fù)雜度主要通過函數(shù)在運(yùn)行時(shí)候顯式申請(qǐng)的額外空間來確定。

??全文總結(jié)

本文主要講解：

1. 算法的定義：算法是解決特定問題求解步驟的描述，在計(jì)算機(jī)中表現(xiàn)為指令的有限序列，并且每條指令表示一個(gè)或多個(gè)操作。
2. 算法的特性：有窮性、確定性、可行性、輸入、輸出。
3. 算法的設(shè)計(jì)要求：正確性、可讀性、健壯性、高效率和低存儲(chǔ)量需求。
4. 算法的度量方法：事后統(tǒng)計(jì)方法、事前分析估算方法。
5. 推導(dǎo)大O階
6. 時(shí)間復(fù)雜度
7. 空間復(fù)雜度

???? 今天的干貨分享到這里就結(jié)束啦！如果覺得文章還可以的話，希望能給個(gè)三連支持一下，聆風(fēng)吟的主頁還有很多有趣的文章，歡迎小伙伴們前去點(diǎn)評(píng)，您的支持就是作者前進(jìn)的最大動(dòng)力！
文章來源地址http://www.zghlxwxcb.cn/news/detail-803320.html

到了這里，關(guān)于【圖解數(shù)據(jù)結(jié)構(gòu)】深入剖析時(shí)間復(fù)雜度與空間復(fù)雜度的奧秘的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！