C語言數據結構時間復雜度及空間復雜度簡要分析

一、時間復雜度和空間復雜度是什麼?

1.1算法效率定義

算法效率分為兩種,一種是時間效率——時間復雜度,另一種是空間效率——空間復雜度

1.2時間復雜度概念

時間復雜度,簡言之就是你寫一個代碼,它解決一個問題上需要走多少步驟,需要花費多長時間。打個簡單的比方:現在給10個數,要求找到7在哪裡1,2,3,4,5,6,7,8,9,10。我們要求寫一個代碼,同學狗蛋寫瞭一個暴力查找,從第一個數依次往後遍歷,他的算法要找7次,同學狗剩寫瞭一個二分法查找,隻要找2次,這就是時間復雜度的比較
算法中的基本操作的執行次數,為算法的時間復雜度

1.3空間復雜度概念

空間復雜度,是對一個算法在運行過程中臨時占用存儲空間大小的量度。舉個栗子:我們現在要求寫一個代碼,狗蛋啪啪啪敲瞭一大堆變量,程序運行瞭,狗剩就用瞭很少的變量,程序也運行瞭。但是他們兩個在代碼運行中變量多少不同,占用的內存多少是不一樣的。空間復雜度,它計算的是變量的個數。

二、如何計算常見算法的時間復雜度和空間復雜度

我們在計算時間/空間復雜度時用的都是大O漸進表示法(是一種估算法)

2.1時間復雜度計算

我們以一個簡單的函數舉例
代碼如下:

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++;
	}
}

試問:該函數如果被調用,要運行多少次?
我們清楚的看出i進去有n次,共有n個i,第一個for結束要運行n^ 2次,第二個for要執行3n-1次,共執行n^ 2+3n-1次
那麼我們這裡的時間復雜度是否就是n^2+3n-1呢?答案是否的
我們前面說過,時間復雜度和空間復雜度用的都是大O漸進表示法,是一種估算法

我們取的值,是取對表達式中影響最大的那個

我們以n^ 2+3 * n-1這個式子進行舉例:設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(n)影響最大的是n^ 2,設g(n)=n^2
n=1,g(n)=1
n=10,g(n)=100
n=100,g(n)=10000
n=1000,g(n)=1000000

當n越大,g(n)就越接近f(n)
那麼這裡的時間復雜度大O漸進表達法寫法是這樣的:O(n^2)

2.2空間復雜度計算

在學習空間復雜度的求解之前,我們要知道,空間復雜度也是用大O漸進表達法進行求解,我們計算的不是所占空間大小,而是變量的個數。先來看一段代碼:
代碼如下(示例):

#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;
	}
}

在上面這個代碼中,我們創建瞭三個變量分別是size_t endint exchangesize_t i,盡管我們這個函數會經歷很多的循環,但這三個變量是反復使用的,也就是說他們所占的空間是被反復使用的,空間的多少是沒有變的,這裡區別時間復雜度——時間是累計的,空間是不累計的(對於時間復雜度,每次循環都會被計算;對於空間復雜度,空間是可以被反復使用的)。

我們上面說過,空間復雜度計算也是用的大O漸進表示法,對於常數,我們統一用O(1)表示(大O漸進表示法詳情見時間和空間復雜度篇1)

ps1:assert通常用於診斷程序中潛在的BUG,通過使用assert(condition), 當condition為false時,程序提前結束運行,利於程序BUG的定位。
ps2:size_t是一種類型,把它看作long unsigned int

我們再來看一段代碼:
代碼如下(示例):

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

這段代碼是一個很簡單的遞歸實現階乘運算,那麼它的空間復雜度是多少呢?我們先假設傳過去的n=10。

在這裡插入圖片描述

10傳過來我們會進行10次遞歸,每次遞歸是創建一個函數棧幀(也就是一個空間),共創建10次,每一次的空間復雜度都是O(1)。把10換成n,也就是進行n次遞歸,每次遞歸會創建1個函數棧幀,空間復雜度是O(n)。

ps:可能會有小夥伴問,那函數棧幀遞歸往回走的時候不是銷毀瞭嗎?註意:這裡的空間復雜度是計算的“最壞、最多的情況”,況且不管是什麼函數,在使用過後其棧幀都會銷毀,空間復雜度算的是它用的空間最多的時候。

2.3快速推倒大O漸進表達法

1.常數1代替所有加法運算中的常數
2.隻保留最高階(高數極限思想)
3.若最高階存在且不為常數,則去除最高階的系數,比如3*n^ 9,去掉系數變為n^9

我們再來看兩個代碼訓練一下
代碼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漸進表達法就是O(n)

代碼2如下:

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

這裡一眼就看出是運行1000次,用什麼來表示呢?前面說過:常數1代替所有加法運算中的常數,所以這裡不管常數有多大,隻要你隻有一個常數都用O(1)表示

一些註意事項:

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

O(n)這個時間復雜度是隨n改變的
打個通俗的比方:設一個函數O(x)=1,那你x隨意多少,函數值都是1
設一個函數O(X)=x,那這裡函數值就隨x變換而變換瞭

三、一些特殊的情況

有些算法的時間復雜度是存在最好、平均、最壞情況:
最壞情況:任意輸入規模的最大運行次數(上界)
平均情況:任意輸入規模的期望運行次數
最好情況:任意輸入規模的最小運行次數(下界)
不多說,舉例說明:
代碼如下:

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

上面的代碼是一個簡單的查找字符的函數,比如我們現在給一串字符共n個字符“aaaaba…aaac”(省略號省略a)
這裡查找a一下子就找到瞭,查找b要點功夫,查找c就更慢瞭,如果查找d,不好意思,查無此d。
那麼這裡就出現瞭最好情況:一次找到O(1)
平均情況:O(n/2)
最差情況:O(n)
對於這裡最壞情況可能有同學要說為什麼是O(n),你看最壞情況沒找到不是嗎?這裡解釋是這樣的,你找c要n次,找d是找不到也要找n次才能確定找不到。

總結

本文介紹瞭時間和空間復雜度的定義及大O漸進表達法的算法及一些特殊情況的解釋,希望對屏幕前的讀者有所幫助,祝您學習愉快!

更多關於數據結構時間復及空間復雜度的資料請關註WalkonNet其它相關文章!

推薦閱讀: