一.算法的時(shí)間復(fù)雜度和空間復(fù)雜度

1.算法效率

算法的復(fù)雜度：

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

2.時(shí)間復(fù)雜度

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

時(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ù)雜度。

實(shí)際中我們計(jì)算時(shí)間復(fù)雜度時(shí)，我們其實(shí)并不一定要計(jì)算精確的執(zhí)行次數(shù)，而只需要大概執(zhí)行次數(shù)，那么這里我們使用大O的漸進(jìn)表示法。

1.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)存在且不是1，則去除與這個(gè)項(xiàng)目相乘的常數(shù)。得到的結(jié)果就是大O階。

在實(shí)際中一般情況關(guān)注的是算法的最壞運(yùn)行情況，所以數(shù)組中搜索數(shù)據(jù)時(shí)間復(fù)雜度為O(N)。

1.3常見例題

void Func1(int N){	int count = 0;	for (int k = 0; k < 2 * N; ++k)	{		++count;	}	int M = 10;	while (M--)	{		++count;	}	printf("%d/n", count);}

基本操作執(zhí)行了2N+10次，通過推導(dǎo)大O階方法知道，時(shí)間復(fù)雜度為 O(N)

void Func2(int N, int M){	int count = 0;	for (int k = 0; k < M; ++k)	{		++count;	}	for (int k = 0; k < N; ++k)	{		++count;	}	printf("%d/n", count);}

基本操作執(zhí)行了M+N次，有兩個(gè)未知數(shù)M和N，時(shí)間復(fù)雜度為 O(N+M)

void Func4(int N){ int count = 0; for (int k = 0; k < 100; ++ k) { ++count; } printf("%d/n", count);}

基本操作執(zhí)行了10次，通過推導(dǎo)大O階方法，時(shí)間復(fù)雜度為 O(1)

// 計(jì)算strchr的時(shí)間復(fù)雜度？const char * strchr ( const char * str, int character );

基本操作執(zhí)行最好1次，最壞N次，時(shí)間復(fù)雜度一般看最壞，時(shí)間復(fù)雜度為 O(N)

// 計(jì)算BubbleSort的時(shí)間復(fù)雜度？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;	}}

基本操作執(zhí)行最好N次，最壞執(zhí)行了(N*(N+1)/2次，通過推導(dǎo)大O階方法+時(shí)間復(fù)雜度一般看最
壞，時(shí)間復(fù)雜度為 O(N^2)

// 計(jì)算BinarySearch的時(shí)間復(fù)雜度？int BinarySearch(int* a, int n, int x){	assert(a);	int begin = 0;	int end = n - 1;	while (begin < end)	{		int mid = begin + ((end - begin) >> 1);		if (a[mid] < x)			begin = mid + 1;		else if (a[mid] > x)			end = mid;		else			return mid;	}	return -1;}

操作執(zhí)行最好1次，最壞O(logN)次，時(shí)間復(fù)雜度為 O(logN) ps：logN在算法分析中表示是底數(shù)為2，對(duì)數(shù)為N。有些地方會(huì)寫成lgN。（折紙查找計(jì)算出來）

// 計(jì)算階乘遞歸Fac的時(shí)間復(fù)雜度？long long Fac(size_t N){ if(0 == N) return 1;  return Fac(N-1)*N;}

基本操作遞歸了N次，時(shí)間復(fù)雜度為O(N)。

8

// 計(jì)算斐波那契遞歸Fib的時(shí)間復(fù)雜度？long long Fib(size_t N){ if(N < 3) return 1;  return Fib(N-1) + Fib(N-2);}

基本操作遞歸了2^N次，時(shí)間復(fù)雜度為O(2^N)。

3.空間復(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)的額外空間來確定。

// 計(jì)算BubbleSort的空間復(fù)雜度？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; }}

使用了常數(shù)個(gè)額外空間，所以空間復(fù)雜度為 O(1)

// 計(jì)算Fibonacci的空間復(fù)雜度？// 返回斐波那契數(shù)列的前n項(xiàng)long long* Fibonacci(size_t n){	if (n == 0)		return NULL;	long long * fibArray = (long long *)malloc((n + 1) * sizeof(long long));	fibArray[0] = 0;	fibArray[1] = 1;	for (int i = 2; i <= n; ++i)	{		fibArray[i] = fibArray[i - 1] + fibArray[i - 2];	}	return fibArray;}

動(dòng)態(tài)開辟了N個(gè)空間，空間復(fù)雜度為 O(N)

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

遞歸調(diào)用了N次，開辟了N個(gè)棧幀，每個(gè)棧幀使用了常數(shù)個(gè)空間。空間復(fù)雜度為O(N)

4. 常見復(fù)雜度對(duì)比

二.順序表和鏈表

1.線性表

線性表（linear list）是n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列。 線性表是一種在實(shí)際中廣泛使用的數(shù)據(jù)結(jié)
構(gòu)，常見的線性表：順序表、鏈表、棧、隊(duì)列、字符串…線性表在邏輯上是線性結(jié)構(gòu)，也就說是連續(xù)的一條直線。但是在物理結(jié)構(gòu)上并不一定是連續(xù)的，線性表在物理上存儲(chǔ)時(shí)，通常以數(shù)組和鏈?zhǔn)浇Y(jié)構(gòu)的形式存儲(chǔ)。

順序表：

鏈表：

2.順序表

2.1 順序表概念

順序表是用一段物理地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素的線性結(jié)構(gòu)，一般情況下采用數(shù)組存儲(chǔ)。在數(shù)組
上完成數(shù)據(jù)的增刪查改。

靜態(tài)順序表：

#define N 10typedef int SLDataType;//方便更改存儲(chǔ)類型typedef struct SeqList{	SLDataType arr[N];//定長(zhǎng)數(shù)組	int size;//有效數(shù)據(jù)個(gè)數(shù)}SeqList;

動(dòng)態(tài)順序表：

typedef int SLDataType;//方便更改存儲(chǔ)類型typedef struct SeqList{	SLDataType* arr;//指向動(dòng)態(tài)開辟的數(shù)字	int size;//有效數(shù)據(jù)個(gè)數(shù)	int capicity;// 容量空間大小}SeqList;

2.2 順序表的增刪查改

靜態(tài)順序表只適用于確定知道需要存多少數(shù)據(jù)的場(chǎng)景。靜態(tài)順序表的定長(zhǎng)數(shù)組導(dǎo)致N定大了，空間開多了浪
費(fèi)，開少了不夠用。所以現(xiàn)實(shí)中基本都是使用動(dòng)態(tài)順序表，根據(jù)需要?jiǎng)討B(tài)的分配空間大小，所以下面我們實(shí)
現(xiàn)動(dòng)態(tài)順序表。

@@@順序表代碼傳送門@@@

2.3 順序表的缺點(diǎn)

1. 中間/頭部的插入刪除，時(shí)間復(fù)雜度為O(N)
2. 增容需要申請(qǐng)新空間，拷貝數(shù)據(jù)，釋放舊空間。會(huì)有不小的消耗。
3. 增容一般是呈2倍的增長(zhǎng)，勢(shì)必會(huì)有一定的空間浪費(fèi)。例如當(dāng)前容量為100，滿了以后增容到200，我們
   再繼續(xù)插入了5個(gè)數(shù)據(jù)，后面沒有數(shù)據(jù)插入了，那么就浪費(fèi)了95個(gè)數(shù)據(jù)空間。
   思考：如何解決以上問題呢？下面給出了鏈表的結(jié)構(gòu)來看看。

3.鏈表

3.1 鏈表概念

鏈表是一種物理存儲(chǔ)結(jié)構(gòu)上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈
接次序?qū)崿F(xiàn)的 。

注意：
1.鏈表的存儲(chǔ)在邏輯上連續(xù)，在物理上不一定連續(xù)
2.結(jié)點(diǎn)一般從堆上申請(qǐng)

3.2 鏈表的分類

1.單項(xiàng)或雙向鏈表

2.帶頭或不帶頭鏈表

3.循環(huán)或非循環(huán)鏈表

雖然有這么多的鏈表的結(jié)構(gòu)，但是我們實(shí)際中最常用還是兩種結(jié)構(gòu)
1.無頭單向不循環(huán)鏈表（OJ題基本都是）
2.帶頭雙項(xiàng)循環(huán)鏈表

3.3 無頭單向不循環(huán)鏈表

無頭單向非循環(huán)鏈表：結(jié)構(gòu)簡(jiǎn)單，一般不會(huì)多帶帶用來存數(shù)據(jù)。實(shí)際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)，如哈希桶、圖的鄰接表等等。另外這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多。

@@@單鏈表代碼傳送門@@@

3.4帶頭雙向循環(huán)鏈表

帶頭雙向循環(huán)鏈表：結(jié)構(gòu)最復(fù)雜，一般用在多帶帶存儲(chǔ)數(shù)據(jù)。實(shí)際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都是帶頭雙向循環(huán)鏈表。另外這個(gè)結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜，但是使用代碼實(shí)現(xiàn)以后會(huì)發(fā)現(xiàn)結(jié)構(gòu)會(huì)帶來很多優(yōu)勢(shì)，實(shí)現(xiàn)反而 簡(jiǎn)單了。

@@@雙向鏈表代碼傳送門@@@

4.順序表和鏈表的區(qū)別和聯(lián)系

不同點(diǎn)
1.存儲(chǔ)空間上：

順序表：物理上一定連續(xù)
鏈表：邏輯上連續(xù)，物理上不一定連續(xù)

2.隨機(jī)訪問：

順序表：支持 O（1）
鏈表：不支持O（N）

3.任意位置的插入或刪除：

順序表：可能需要搬移元素，效率低 O（N）
鏈表：只需要修改指針

4.插入：

順序表：動(dòng)態(tài)表可以擴(kuò)容
鏈表:需要的時(shí)候在棧上申請(qǐng)

5.應(yīng)用場(chǎng)景：

順序表：元素高效存儲(chǔ)和頻繁訪問
鏈表：任意位置插入刪除頻繁

6.緩存利用率

順序表：高
鏈表：低

附上鏈表高頻面試題詳情解析，方便大家理解與使用鏈表

單鏈表經(jīng)典面試題第一篇

單鏈表經(jīng)典面試題第二篇