一、時(shí)間復(fù)雜度

1）O(n)的含義

• 程序消耗的時(shí)間用算法的操作單元數(shù)來(lái)表示
• 假設(shè)數(shù)據(jù)的規(guī)模為n，則用f(n)表示操作單元數(shù)的大小，而f(n)常被簡(jiǎn)化
• O表示的是一般的情況，而不是上界或下界。并且它是在數(shù)據(jù)量級(jí)非常大的情況下所展現(xiàn)出的時(shí)間復(fù)雜度
• 因?yàn)镺代表的是一個(gè)一般的情況，所以當(dāng)用例不同時(shí)，算法的時(shí)間復(fù)雜度不同，需要具體分析

2）復(fù)雜表達(dá)式的簡(jiǎn)化

表達(dá)式簡(jiǎn)化遵循以下兩個(gè)原則：

• 去掉常數(shù)項(xiàng)
• 只保留最高項(xiàng)

為例分析：

• 去掉常數(shù)項(xiàng)后為
• 只保留最高項(xiàng)后為

不難想象，當(dāng)n趨一個(gè)非常大的數(shù)量級(jí)的時(shí)候，最高項(xiàng)將其決定性作用。但是若常數(shù)項(xiàng)也是一個(gè)非常大的數(shù)量級(jí)，那我們就不可以輕易將其舍去。

3）O(n)不一定優(yōu)于O(n^2)

        由上面簡(jiǎn)化法則我們可以看到，常數(shù)項(xiàng)是被忽略的，如與，當(dāng)n < 20時(shí)前者的操作單位數(shù)是小于后者的。

所以在決定使用什么算法的時(shí)候并不是算法的時(shí)間復(fù)雜度越低越好，還需要考慮數(shù)據(jù)的規(guī)模

        那為什么我們默認(rèn)時(shí)間復(fù)雜度低于呢？正如前面提到的關(guān)于O的定義：它是在數(shù)據(jù)量級(jí)非常大的情況下所展現(xiàn)出的時(shí)間復(fù)雜度，所以我們默認(rèn)前者的時(shí)間復(fù)雜度更優(yōu)。

?4）遞歸的時(shí)間復(fù)雜度

?遞歸的時(shí)間復(fù)雜度 = 遞歸次數(shù) X 每次遞歸的操作次數(shù)。

現(xiàn)在我們從一道面試題來(lái)分析時(shí)間復(fù)雜度：求x的n次方

①直觀(guān)的for循環(huán)遍歷

int fuc1(int n)
{
	int ret = 1;
	for (int i = 1; i < n; i++)
		ret *= i;
	return ret;
}

【分析】時(shí)間復(fù)雜度為O(n)，因?yàn)椴僮鲉卧獢?shù)為n次?

②遞歸版本1

int fuc2(int n,int x)
{
	if (n == 0)
		return 1;
	if (n == 1)
		return x;
	return x * fuc2(n - 1, x);
}

【分析】遞歸次數(shù)為n次，每次相乘的時(shí)間復(fù)雜度為O(1)，所以時(shí)間復(fù)雜度仍為O(n)

?③遞歸版本2?

int fuc3(int n, int x)
{
	if (n == 0)
		return 1;
	if (n == 1)
		return x;
	if (n % 2 == 1)
		return fuc3(n / 2, x) * fuc3(n / 2, x) * x;//奇數(shù)次冪的情況
	return fuc3(n / 2, x) * fuc3(n / 2, x);		   //偶數(shù)次冪的情況
}

【分析】上面代碼的時(shí)間復(fù)雜度為嗎？我們可以畫(huà)二叉樹(shù)來(lái)理解，以n = 16為例?

每一個(gè)結(jié)點(diǎn)都表示需要進(jìn)行一次遞歸，因此結(jié)點(diǎn)數(shù)代表著遞歸次數(shù)，所以先我們計(jì)算二叉樹(shù)結(jié)點(diǎn)數(shù)?

• 一顆滿(mǎn)二叉樹(shù)的結(jié)點(diǎn)數(shù)根據(jù)等比數(shù)列求和公式可以求出為：?（m為二叉樹(shù)深度）?
• 二叉樹(shù)深度m 計(jì)算公式?：（向下取整）?

        因?yàn)閚為奇數(shù)時(shí)我們將其拆成偶數(shù)處理，如：

將深度公式代入結(jié)點(diǎn)總和公式我們可以得出， 節(jié)點(diǎn)數(shù) = n - a（a為某個(gè)常數(shù)），所以時(shí)間復(fù)雜度還是

④遞歸版本3?

int fuc4(int n, int x)
{
	if (n == 0)
		return 1;
	else if (n == 1)
		return 1;
	int t = fuc4(n / 2, x);
	if (n % 2 == 1)
		return t * t * x;
	return t * t;
}

通過(guò)將遞歸操作抽離出來(lái)從而減少遞歸次數(shù)，我們真正實(shí)現(xiàn)了時(shí)間復(fù)雜度為?

我們?cè)俜治鲆幌虑箪巢瞧鯏?shù)列函遞歸解法時(shí)間復(fù)雜度：?

int fib(int n)
{
	if (n <= 0)
		return 1;
	if (n == 1)
		return 1;
	return fib(n - 1) + fib(n - 2);
}

同樣的我們可以畫(huà)二叉樹(shù)來(lái)分析。求第k個(gè)斐波那契數(shù)，我們不難想象，我們將構(gòu)造出一個(gè)深度為k的二叉樹(shù)，深度為k的二叉樹(shù)最多有個(gè)結(jié)點(diǎn)，所以我們得出該算法的時(shí)間復(fù)雜度為。優(yōu)化的思路和上述求x的n次方的思路一樣，主要是減少遞歸的調(diào)用次數(shù)?

int fib(int first, int second, int n)
{
	if (n <= 0)
		return 0;
	if (n < 3)
		return 1;
	else if (n == 3)
		return first + second;
	else
		return fib(second, first + second, n - 1);
}

二、空間復(fù)雜度

1）O(1)空間復(fù)雜度?

程序占用空間不隨n的變化而變化，即占用的空間是一個(gè)常數(shù)?

for(int j = 0; j < n; j++)
{
	j++;
}

程序占用的空間與n無(wú)關(guān)，上圖中之涉及為j分配內(nèi)存空間，是一個(gè)固定的常量?

2）???????O(n)空間復(fù)雜度?

程序占用空間隨n增長(zhǎng)而線(xiàn)性增長(zhǎng)；?

int arr[n];

3）???????O(mn)空間 復(fù)雜度?

常常是定義一個(gè)二維集合，集合的大小與集合的長(zhǎng)與寬相管?

int arr[row * col];

4）遞歸算法空間算法復(fù)雜度分析?

?遞歸算法空間復(fù)雜度 = 每次遞歸的空間復(fù)雜度 X 遞歸深度（遞歸調(diào)用棧的最大長(zhǎng)度）

我們同樣來(lái)分析上面提到的求斐波那契數(shù)函數(shù)的空間復(fù)雜度：?

int f(int n)
{
	if (n <= 0)
		return 1;
	if (n == 1)
		return 1;
	return f(n - 1) + f(n - 2);
}

在遞歸的過(guò)程中依次將f(5)，f(4)， f(3)，f(2)，f(1)壓棧，每一次調(diào)用所占用的空間都為所以占用的空間為，所以上述代碼的空間復(fù)雜度為?

我們?cè)賮?lái)分析遞歸實(shí)現(xiàn)的二分查找的空間復(fù)雜度?：

int binary_search(int arr[], int l, int r, int x)
{
	if (r >= l)
	{
		int mid = l + (r - l) / 2; //避免先加后除產(chǎn)生溢出的錯(cuò)誤
		if (arr[mid] == x)
			return mid;
		else if (arr[mid] < x)
			return binary_search(arr, mid + 1, r ,x);
		else
			return binary_search(arr, l, mid - 1, x);
	}
	return -1;
}

每次遞歸所占用的空間都是一定的，所以每次遞歸的空間復(fù)雜度為，而遞歸的最大深度為，所以空間復(fù)雜度為

到此這篇關(guān)于C語(yǔ)言三分鐘精通時(shí)間復(fù)雜度與空間復(fù)雜度的文章就介紹到這了,更多相關(guān)C語(yǔ)言 時(shí)間復(fù)雜度內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論