一.算法的時間復雜度和空間復雜度

1.算法效率

算法的復雜度：

1.算法在編寫成可執(zhí)行程序后，運行 時需要耗費時間資源和空間(內(nèi)存)資源 。因此衡量一個算法的好壞，一般是從時間和空間兩個維度來衡量的，即時間復雜度和空間復雜度。
2.時間復雜度主要衡量一個算法的運行快慢，而空間復雜度主要衡量一個算法運行所需要的額外空間。在計算機發(fā)展的早期，計算機的存儲容量很小。所以對空間復雜度很是在乎。但是經(jīng)過計算機行業(yè)的迅速發(fā)展，計算機的存儲容量已經(jīng)達到了很高的程度。所以我們?nèi)缃褚呀?jīng)不需要再特別關注一個算法的空間復雜度。

2.時間復雜度

1.1時間復雜度的概念

時間復雜度的定義：

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

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

1.2大O的漸進表示法

大O符號（Big O notation）：是用于描述函數(shù)漸進行為的數(shù)學符號。 推導大O階方法：
1、用常數(shù)1取代運行時間中的所有加法常數(shù)。
2、在修改后的運行次數(shù)函數(shù)中，只保留最高階項。
3、如果最高階項存在且不是1，則去除與這個項目相乘的常數(shù)。得到的結(jié)果就是大O階。

在實際中一般情況關注的是算法的最壞運行情況，所以數(shù)組中搜索數(shù)據(jù)時間復雜度為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次，通過推導大O階方法知道，時間復雜度為 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次，有兩個未知數(shù)M和N，時間復雜度為 O(N+M)

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

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

// 計算strchr的時間復雜度？const char * strchr ( const char * str, int character );

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

// 計算BubbleSort的時間復雜度？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次，通過推導大O階方法+時間復雜度一般看最
壞，時間復雜度為 O(N^2)

// 計算BinarySearch的時間復雜度？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)次，時間復雜度為 O(logN) ps：logN在算法分析中表示是底數(shù)為2，對數(shù)為N。有些地方會寫成lgN。（折紙查找計算出來）

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

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

8

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

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

3.空間復雜度

空間復雜度也是一個數(shù)學表達式，是對一個算法在運行過程中臨時占用存儲空間大小的量度 。
空間復雜度不是程序占用了多少bytes的空間，因為這個也沒太大意義，所以空間復雜度算的是變量的個數(shù)?？臻g復雜度計算規(guī)則基本跟實踐復雜度類似，也使用大O漸進表示法。

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

// 計算BubbleSort的空間復雜度？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ù)個額外空間，所以空間復雜度為 O(1)

// 計算Fibonacci的空間復雜度？// 返回斐波那契數(shù)列的前n項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;}

動態(tài)開辟了N個空間，空間復雜度為 O(N)

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

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

4. 常見復雜度對比

二.順序表和鏈表

1.線性表

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

順序表：

鏈表：

2.順序表

2.1 順序表概念

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

靜態(tài)順序表：

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

動態(tài)順序表：

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

2.2 順序表的增刪查改

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

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

2.3 順序表的缺點

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

3.鏈表

3.1 鏈表概念

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

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

3.2 鏈表的分類

1.單項或雙向鏈表

2.帶頭或不帶頭鏈表

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

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

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

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

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

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

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

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

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

不同點
1.存儲空間上：

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

2.隨機訪問：

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

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

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

4.插入：

順序表：動態(tài)表可以擴容
鏈表:需要的時候在棧上申請

5.應用場景：

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

6.緩存利用率

順序表：高
鏈表：低

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

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

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