一、時(shí)間復(fù)雜度和空間復(fù)雜度是什么？

1.1算法效率定義

算法效率分為兩種，一種是時(shí)間效率——時(shí)間復(fù)雜度，另一種是空間效率——空間復(fù)雜度

1.2時(shí)間復(fù)雜度概念

時(shí)間復(fù)雜度，簡(jiǎn)言之就是你寫一個(gè)代碼，它解決一個(gè)問題上需要走多少步驟，需要花費(fèi)多長(zhǎng)時(shí)間。打個(gè)簡(jiǎn)單的比方：現(xiàn)在給10個(gè)數(shù)，要求找到7在哪里1,2,3,4,5,6,7,8,9,10。我們要求寫一個(gè)代碼，同學(xué)狗蛋寫了一個(gè)暴力查找，從第一個(gè)數(shù)依次往后遍歷，他的算法要找7次，同學(xué)狗剩寫了一個(gè)二分法查找，只要找2次，這就是時(shí)間復(fù)雜度的比較
算法中的基本操作的執(zhí)行次數(shù)，為算法的時(shí)間復(fù)雜度

1.3空間復(fù)雜度概念

空間復(fù)雜度，是對(duì)一個(gè)算法在運(yùn)行過程中臨時(shí)占用存儲(chǔ)空間大小的量度。舉個(gè)栗子：我們現(xiàn)在要求寫一個(gè)代碼，狗蛋啪啪啪敲了一大堆變量，程序運(yùn)行了，狗剩就用了很少的變量，程序也運(yùn)行了。但是他們兩個(gè)在代碼運(yùn)行中變量多少不同，占用的內(nèi)存多少是不一樣的。空間復(fù)雜度，它計(jì)算的是變量的個(gè)數(shù)。

二、如何計(jì)算常見算法的時(shí)間復(fù)雜度和空間復(fù)雜度

我們?cè)谟?jì)算時(shí)間/空間復(fù)雜度時(shí)用的都是大O漸進(jìn)表示法（是一種估算法）

2.1時(shí)間復(fù)雜度計(jì)算

我們以一個(gè)簡(jiǎn)單的函數(shù)舉例
代碼如下：

void func1(int n)
{
	int i = 0;
	int j = 0;
	int k = 0;
	int count = 0;
	for (i = 0;i < n;i++)
	{
		for (j = 0;j < n;j++)
		{
			count++;
		}
	}
	for (k = 0;k < 3 * n - 1;k++)
	{
		count++;
	}
}

試問：該函數(shù)如果被調(diào)用，要運(yùn)行多少次？
我們清楚的看出i進(jìn)去有n次，共有n個(gè)i，第一個(gè)for結(jié)束要運(yùn)行n^ 2次，第二個(gè)for要執(zhí)行3n-1次，共執(zhí)行n^ 2+3n-1次
那么我們這里的時(shí)間復(fù)雜度是否就是n^2+3n-1呢？答案是否的
我們前面說過，時(shí)間復(fù)雜度和空間復(fù)雜度用的都是大O漸進(jìn)表示法，是一種估算法

我們?nèi)〉闹?，是取?duì)表達(dá)式中影響最大的那個(gè)

我們以n^ 2+3 * n-1這個(gè)式子進(jìn)行舉例：設(shè)f(n)=n^2+3n-1
n=1,f(n)=1+3-1=3
n=10,f(n)=100+30-1=129
n=100,f(n)=10000+300-1=10299
n=1000,f(n)=1002999
…
很容易發(fā)現(xiàn)，對(duì)f(n)影響最大的是n^ 2,設(shè)g（n）=n^2
n=1,g(n)=1
n=10,g(n)=100
n=100,g(n)=10000
n=1000,g(n)=1000000
…
當(dāng)n越大，g（n）就越接近f（n）
那么這里的時(shí)間復(fù)雜度大O漸進(jìn)表達(dá)法寫法是這樣的：O(n^2)

2.2空間復(fù)雜度計(jì)算

在學(xué)習(xí)空間復(fù)雜度的求解之前，我們要知道，空間復(fù)雜度也是用大O漸進(jìn)表達(dá)法進(jìn)行求解，我們計(jì)算的不是所占空間大小，而是變量的個(gè)數(shù)。先來看一段代碼：
代碼如下（示例）：

#include<stdio.h>
void bubblesort(int*a, int n)
{
	assert(a);
	for (size_t end = n;end > 0;--end)
	{
		int exchange = 0;
		for (size_t i = 1;i < end;++i)
		{
			if (a[i - 1] > a[i])
				swap(&a[i - 1], &a[i]);
			exchange = 1;
		}
		if (exchange == 0)
			break;
	}
}

在上面這個(gè)代碼中，我們創(chuàng)建了三個(gè)變量分別是size_t end、int exchange、size_t i，盡管我們這個(gè)函數(shù)會(huì)經(jīng)歷很多的循環(huán)，但這三個(gè)變量是反復(fù)使用的，也就是說他們所占的空間是被反復(fù)使用的，空間的多少是沒有變的,這里區(qū)別時(shí)間復(fù)雜度——時(shí)間是累計(jì)的，空間是不累計(jì)的（對(duì)于時(shí)間復(fù)雜度，每次循環(huán)都會(huì)被計(jì)算；對(duì)于空間復(fù)雜度，空間是可以被反復(fù)使用的）。

我們上面說過，空間復(fù)雜度計(jì)算也是用的大O漸進(jìn)表示法，對(duì)于常數(shù)，我們統(tǒng)一用O(1)表示（大O漸進(jìn)表示法詳情見時(shí)間和空間復(fù)雜度篇1）

ps1:assert通常用于診斷程序中潛在的BUG，通過使用assert(condition)， 當(dāng)condition為false時(shí)，程序提前結(jié)束運(yùn)行，利于程序BUG的定位。
ps2:size_t是一種類型，把它看作long unsigned int

我們?cè)賮砜匆欢未a：
代碼如下（示例）：

//計(jì)算bubblesort的空間復(fù)雜度
#include<stdio.h>
long long Factorial(size_t n)
{
	return N < 2 ? N : Factorial(n - 1)*n;
}

這段代碼是一個(gè)很簡(jiǎn)單的遞歸實(shí)現(xiàn)階乘運(yùn)算，那么它的空間復(fù)雜度是多少呢？我們先假設(shè)傳過去的n=10。

10傳過來我們會(huì)進(jìn)行10次遞歸，每次遞歸是創(chuàng)建一個(gè)函數(shù)棧幀（也就是一個(gè)空間），共創(chuàng)建10次，每一次的空間復(fù)雜度都是O（1）。把10換成n，也就是進(jìn)行n次遞歸，每次遞歸會(huì)創(chuàng)建1個(gè)函數(shù)棧幀，空間復(fù)雜度是O(n)。

ps：可能會(huì)有小伙伴問，那函數(shù)棧幀遞歸往回走的時(shí)候不是銷毀了嗎？注意：這里的空間復(fù)雜度是計(jì)算的“最壞、最多的情況”，況且不管是什么函數(shù)，在使用過后其棧幀都會(huì)銷毀，空間復(fù)雜度算的是它用的空間最多的時(shí)候。

2.3快速推倒大O漸進(jìn)表達(dá)法

1.常數(shù)1代替所有加法運(yùn)算中的常數(shù)
2.只保留最高階（高數(shù)極限思想）
3.若最高階存在且不為常數(shù)，則去除最高階的系數(shù)，比如3*n^ 9，去掉系數(shù)變?yōu)閚^9

我們?cè)賮砜磧蓚€(gè)代碼訓(xùn)練一下
代碼1如下：

void func2(int n)
{
	int i = 0;
	int k = 0;
	int count = 0;
	for (i = 0;i < 3n;i++)
	{
		count++;
	}
	for (k = 0;k < 6;k++)
	{
		count++;
	}
}

這里f（n）=3n+6，它的大O漸進(jìn)表達(dá)法就是O（n）

代碼2如下：

void func3(int n)
{
	int i = 0;
	int count = 0;
	for (i = 0;i < 1000;i++)
	{
		count++;
	}
}

這里一眼就看出是運(yùn)行1000次，用什么來表示呢？前面說過：常數(shù)1代替所有加法運(yùn)算中的常數(shù)，所以這里不管常數(shù)有多大，只要你只有一個(gè)常數(shù)都用O(1)表示

一些注意事項(xiàng)：

O(1)這個(gè)時(shí)間復(fù)雜度的估值是不隨n的改變而改變的，以大白話說，不管你輸入的n是多少，我這個(gè)算法的效率是不變的

O(n)這個(gè)時(shí)間復(fù)雜度是隨n改變的
打個(gè)通俗的比方：設(shè)一個(gè)函數(shù)O(x)=1,那你x隨意多少，函數(shù)值都是1
設(shè)一個(gè)函數(shù)O(X)=x，那這里函數(shù)值就隨x變換而變換了

三、一些特殊的情況

有些算法的時(shí)間復(fù)雜度是存在最好、平均、最壞情況：
最壞情況：任意輸入規(guī)模的最大運(yùn)行次數(shù)（上界）
平均情況：任意輸入規(guī)模的期望運(yùn)行次數(shù)
最好情況：任意輸入規(guī)模的最小運(yùn)行次數(shù)（下界）
不多說，舉例說明：
代碼如下：

const char*strchr(char*str, char c)
{
	while (*str != '\0')
	{
		if (*str == c)
		{
			return str;
		}
		++str;
	}
	return NULL;
}

上面的代碼是一個(gè)簡(jiǎn)單的查找字符的函數(shù)，比如我們現(xiàn)在給一串字符共n個(gè)字符“aaaaba…aaac”（省略號(hào)省略a）
這里查找a一下子就找到了，查找b要點(diǎn)功夫，查找c就更慢了，如果查找d，不好意思，查無此d。
那么這里就出現(xiàn)了最好情況：一次找到O（1）
平均情況：O（n/2）
最差情況：O（n）
對(duì)于這里最壞情況可能有同學(xué)要說為什么是O（n），你看最壞情況沒找到不是嗎？這里解釋是這樣的，你找c要n次，找d是找不到也要找n次才能確定找不到。

總結(jié)

本文介紹了時(shí)間和空間復(fù)雜度的定義及大O漸進(jìn)表達(dá)法的算法及一些特殊情況的解釋，希望對(duì)屏幕前的讀者有所幫助，祝您學(xué)習(xí)愉快！

更多關(guān)于數(shù)據(jù)結(jié)構(gòu)時(shí)間復(fù)及空間復(fù)雜度的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論