一、概念

1.1、算法效率

如何衡量一個(gè)算法的好壞?比如對于以下斐波那契數(shù)列：

long long Fib(int N)
{
	if (N < 3)
		return 1;
	return Fib(N - 1) + Fib(N - 2);
}

斐波那契數(shù)列用遞歸實(shí)現(xiàn)方式非常簡潔，但簡潔一定好嗎？那該如何衡量其好與壞呢？在學(xué)完時(shí)間復(fù)雜度會(huì)為您揭曉。

算法效率分析分為兩種：第一種是時(shí)間效率，第二種是空間效率。時(shí)間效率被稱為時(shí)間復(fù)雜度，而空間效率被稱作空間復(fù)雜度。 時(shí)間復(fù)雜度主要衡量的是一個(gè)算法的運(yùn)行速度，而空間復(fù)雜度主要衡量一個(gè)算法所需要的額外空間，在計(jì)算機(jī)發(fā)展的早期，計(jì)算機(jī)的存儲(chǔ)容量很小。所以對空間復(fù)雜度很是在乎。但是經(jīng)過計(jì)算機(jī)行業(yè)的迅速發(fā)展，計(jì)算機(jī)的存儲(chǔ)容量已經(jīng)達(dá)到了很高的程度。所以我們?nèi)缃褚呀?jīng)不需要再特別關(guān)注一個(gè)算法的空間復(fù)雜度

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

一個(gè)算法所花費(fèi)的時(shí)間與其中語句的執(zhí)行次數(shù)成正比例，算法中的基本操作的執(zhí)行次數(shù)，為算法的時(shí)間復(fù)雜度。

1.3、空間復(fù)雜度

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

二、計(jì)算

2.1、大O的漸進(jìn)表示法

先看一串代碼：

// 請計(jì)算一下Func1基本操作執(zhí)行了多少次？
void Func1(int N)
{
	int count = 0;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			++count;
		}
	}
	for (int k = 0; k < 2 * N; ++k)
	{
		++count;
	}
	int M = 10;
	while (M--)
	{
		++count;
	}
	printf("%d\n", count);
}

算法中的基本操作的執(zhí)行次數(shù)，為算法的時(shí)間復(fù)雜度。顯而易見，這里Func1 執(zhí)行的最準(zhǔn)確操作次數(shù) ：F(N)=N*N+2*N+10

例如F(10)=130、F(100)=10210、F(1000)=1002010

按理來說此題的時(shí)間復(fù)雜度就是上述的公式，其實(shí)不然。時(shí)間復(fù)雜度是一個(gè)估算，是去看表達(dá)式中影響最大的那一項(xiàng)。此題隨著N的增大，這個(gè)表達(dá)式中N^2對結(jié)果的影響是最大的

實(shí)際中我們計(jì)算時(shí)間復(fù)雜度時(shí)，我們其實(shí)并不一定要計(jì)算精確的執(zhí)行次數(shù)，而只需要大概執(zhí)行次

數(shù)，那么這里我們使用大O的漸進(jìn)表示法。，因而上題的時(shí)間復(fù)雜度為O(N^2)

大O符號(hào)（Big O notation）：是用于描述函數(shù)漸進(jìn)行為的數(shù)學(xué)符號(hào)。

推導(dǎo)大O階方法：

• 用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)。
• 在修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高階項(xiàng)。
• 如果最高階項(xiàng)存在且不是1，則去除與這個(gè)項(xiàng)目相乘的常數(shù)。得到的結(jié)果就是大O階。

通過上面我們會(huì)發(fā)現(xiàn)大O的漸進(jìn)表示法去掉了那些對結(jié)果影響不大的項(xiàng)，簡潔明了的表示出了執(zhí)行次數(shù)。另外有些算法的時(shí)間復(fù)雜度存在最好、平均和最壞情況：

• 最壞情況：任意輸入規(guī)模的最大運(yùn)行次數(shù)(上界)
• 平均情況：任意輸入規(guī)模的期望運(yùn)行次數(shù)
• 最好情況：任意輸入規(guī)模的最小運(yùn)行次數(shù)(下界)

例如：在一個(gè)長度為N數(shù)組中搜索一個(gè)數(shù)據(jù)x

• 最好情況：1次找到
• 最壞情況：N次找到
• 平均情況：N/2次找到

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

注意：遞歸算法時(shí)間復(fù)雜度計(jì)算

• 每次函數(shù)調(diào)用是O(1)，那么就看他的遞歸次數(shù)
• 每次函數(shù)調(diào)用不是O(1)，那么就看他的遞歸調(diào)用中次數(shù)的累加

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

例題：

例一：

// 計(jì)算Func2的時(shí)間復(fù)雜度？
void Func2(int N)
{
	int count = 0;
	for (int k = 0; k < 2 * N; ++k)
	{
		++count;
	}
	int M = 10;
	while (M--)
	{
		++count;
	}
	printf("%d\n", count);
}

答案：O(N)

解析：此題中最準(zhǔn)確的次數(shù)為2*N+10，而其中影響最大的是N，可能有人覺著是2*N，但隨著N的不斷增大，2對結(jié)果的影響不是很大，況且要符合上述第三條規(guī)則：如果最高階項(xiàng)存在且不是1，則去除與這個(gè)項(xiàng)目相乘的常數(shù)。得到的結(jié)果就是大O階。所以把2去除掉，因而時(shí)間復(fù)雜度為O(N)

例二：

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

答案：O(M+N)

解析：因?yàn)镸和N都是未知數(shù)，所以N和M都要帶著，但是如果題目明確M遠(yuǎn)大于N，那么時(shí)間復(fù)雜度就是O(M)，如果M和N差不多大，那么時(shí)間復(fù)雜度就是O(M)或O(N)

例三：

// 計(jì)算Func4的時(shí)間復(fù)雜度？
void Func4(int N)
{
	int count = 0;
	for (int k = 0; k < 100; ++k)
	{
		++count;
	}
	printf("%d\n", count);
}

答案：O(1)

解析：這里最準(zhǔn)確的次數(shù)是100，但是要符合大O的漸進(jìn)表示法的規(guī)則，用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)。所以時(shí)間復(fù)雜度就是O(1)

例四：

// 計(jì)算strchr的時(shí)間復(fù)雜度？
const char* strchr(const char* str, char character)
{
	while (*str != '\0')
	{
		if (*str == character)
			return str;
		++str;
	}
	return NULL;
}

答案：O(N)

解析：此題就要分情況了，這里假設(shè)字符串為abcdefghijklmn，如果目標(biāo)字符找的是g，則需要執(zhí)行N/2次，如果找到是a，則需要執(zhí)行1次，如果找n，則N次，所以要分情況，這里就出現(xiàn)了有些算法的時(shí)間復(fù)雜度存在最好O(1)、平均O(N/2)和最壞O(N)情況，但是在實(shí)際中一般情況關(guān)注的是算法的最壞運(yùn)行情況，所以此題時(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;
	}
}

答案：O(N^2)

解析：此段代碼考到的是冒泡排序。第一趟的冒泡排序走了N次，第二趟走了N-1次，第三趟N-2，……最后就是1，次規(guī)律正合等差數(shù)列，求和即為(N+1)*N/2，當(dāng)然這個(gè)是最準(zhǔn)確的，這里還要找對結(jié)果影響最大的那一項(xiàng)，即N^2，所以時(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;
	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;
}

答案：O(logN)

解析：此題很明顯考到的是二分查找。假設(shè)數(shù)組長度為N，且找了X次，則1*2*2*2*2*……*2=N，即為2^X=N，則X等于log以2為底N的對數(shù)，而算法的復(fù)雜度計(jì)算，喜歡省略簡寫成logN，因?yàn)楹芏嗟胤讲缓脤懙讛?shù)，所以此題時(shí)間復(fù)雜度為O(logN)

例七：

// 計(jì)算階乘遞歸Factorial的時(shí)間復(fù)雜度？
long long Factorial(size_t N)
{
return N < 2 ? N : Factorial(N-1)*N;
}

答案：O(N)

解析：如果N為10

例八：

long long Fib(int N)
{
	if (N < 3)
		return 1;
	return Fib(N - 1) + Fib(N - 2);
}

這串代碼是上文最開始呈現(xiàn)的代碼，代碼風(fēng)格十分簡單，短短幾行便可完成斐波那契數(shù)列的計(jì)算，可看似這么簡潔的代碼真的“好”嗎？先來計(jì)算一下時(shí)間復(fù)雜度：

答案：O(2^N)

解析：

 有上圖可以得知，第一行執(zhí)行1次，第二行執(zhí)行2^1次，第三行執(zhí)行2^2次，以此類推，是個(gè)等比數(shù)列，累計(jì)算下來再根據(jù)大O階表示法的規(guī)則得知，此斐波那契數(shù)列的時(shí)間復(fù)雜度為O(2^N)。

但是，根據(jù)2^N這個(gè)時(shí)間復(fù)雜度是個(gè)非常大的數(shù)字，當(dāng)n=10時(shí)，在VS環(huán)境下很快容易得到答案，但是當(dāng)n稍微再大一點(diǎn)比如說是50，就要等上很長一段時(shí)間才能將結(jié)果算出來，由此可見，簡潔的代碼不一定是最優(yōu)的代碼。

 常見時(shí)間復(fù)雜度：O(N^2)、O(N)、O(logN)、O(1)

復(fù)雜度對比：

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

• 空間復(fù)雜度也是一個(gè)數(shù)學(xué)表達(dá)式，是對一個(gè)算法在運(yùn)行過程中臨時(shí)占用存儲(chǔ)空間大小的量度 ?？臻g復(fù)雜度不是程序占用了多少bytes的空間，因?yàn)檫@個(gè)也沒太大意義，所以空間復(fù)雜度算的是變量的個(gè)數(shù)。
• 空間復(fù)雜度計(jì)算規(guī)則基本跟實(shí)踐復(fù)雜度類似，也使用大O漸進(jìn)表示法。
• 注意：函數(shù)運(yùn)行時(shí)所需要的?？臻g(存儲(chǔ)參數(shù)、局部變量、一些寄存器信息等)在編譯期間已經(jīng)確定好了，因此空間復(fù)雜度主要通過函數(shù)在運(yùn)行時(shí)候顯式申請的額外空間來確定。

例題

例一：

// 計(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;
	}
}

答案：O(1)

解析：這里其實(shí)總共開辟了三個(gè)空間，分別為end、exchange、i，既然是常數(shù)個(gè)變量，那么空間復(fù)雜度就是O(1)，空間復(fù)雜度算的是申請的額外空間，所以跟上面的int*a和int n沒有關(guān)系?？赡苡腥擞X著這是個(gè)for循環(huán)，exchange應(yīng)該開辟n次，其實(shí)每次循環(huán)進(jìn)來，exchange都會(huì)重新開辟，結(jié)束一次循環(huán)exchange銷毀，以此類推，exchange始終是同一個(gè)空間。

而什么時(shí)候會(huì)出現(xiàn)O(n)呢？

1、malloc一個(gè)數(shù)組

int *a = (int*)malloc(sizeof(int)*numsSize); //O(N)

此情況的前提是numsSize必須是個(gè)未知的數(shù)字，如果是具體數(shù)字，那么空間復(fù)雜度依舊是O(1)

2、變長數(shù)組

int a[numsSize]; //numsSize未知，O(N)

例二：

// 計(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;
}

答案：O(N+1)

解析：這里看到了malloc開辟了n+1個(gè)大小為long long類型的數(shù)組，看到這就不需要再過多計(jì)較后續(xù)創(chuàng)建了幾個(gè)變量，因?yàn)榭臻g復(fù)雜度是估算，所以直接就是O(N)

例三：

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

答案：O(1)

解析： 這里遞歸函數(shù)是要建立棧幀的，而建立棧幀的個(gè)數(shù)為N個(gè)，每個(gè)棧幀的變量都是常數(shù)個(gè)，N個(gè)即空間復(fù)雜度為O(N)

例四：

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

答案：O(N)

解析：時(shí)間一去不復(fù)返，是累積的，空間回收以后是可以重復(fù)利用的。當(dāng)遞歸到Fib(3)的時(shí)候，此時(shí)調(diào)用Fib(2)和Fib(1)，調(diào)到Fib(2)就可以返回了，此時(shí)Fib(2)的棧幀就銷毀了，此時(shí)再調(diào)用的Fib(1)和Fib(2)用的就是同一塊空間，同理Fib(N-1)總共建立了N-1個(gè)棧幀，同理再調(diào)用Fib(N-2)和剛才Fib(N-1)使用的是同一塊空間，充分說明了時(shí)間一去不復(fù)返，是累積的，空間回收以后是可以重復(fù)利用的。

三、有復(fù)雜度要求的習(xí)題

題一：（消失的數(shù)字）

鏈接：https://leetcode-cn.com/problems/missing-number-lcci/

 此題就明確了一個(gè)要求：想辦法在O(n)的時(shí)間內(nèi)完成，本題將提供兩種有效且可行的方法，正文開始：

法一：相加 - 相加

思想：

此題是在一串連續(xù)的整數(shù)中缺了一個(gè)數(shù)，那我們就把理應(yīng)有的整數(shù)個(gè)數(shù)依次相加再減去原數(shù)組中缺一個(gè)數(shù)字的所有元素和即為我們想要的數(shù)字。

代碼如下：

int missingNumber(int* nums, int numsSize){
    int sum1=0;
    int sum2=0;
    for(int i=0;i<numsSize+1;i++)
    {
        sum1+=i;
    }
    for(int i=0;i<numsSize;i++)
    {
        sum2+=nums[i];
    }
    return sum1-sum2;
}

法二：異或

思想：

正如示例2，這里假設(shè)一共有10個(gè)數(shù)字，那么這里nums數(shù)組就是 [ 0 - 9 ]，不過其中缺了一個(gè)數(shù)字，我們已經(jīng)深知異或的運(yùn)算規(guī)則（相同為0，相異為1）以及兩個(gè)重要結(jié)論：1、兩個(gè)相同的數(shù)字異或等于0。2、0與任何數(shù)字異或等于該任意數(shù)字。因此，我們完全可以先把原數(shù)組的所有元素異或起來，再把理論上0-n依次遞增的所有元素都異或起來，然后兩塊再次異或得到的就是缺少的數(shù)字。

畫圖展示：

 代碼如下：

int missingNumber(int* nums, int numsSize){
    int n=0;
    for(int i=0;i<numsSize;i++)
    {
        n^=nums[i];
    }
    for(int i=0;i<numsSize+1;i++)
    {
        n^=i;
    }
    return n;
}

注意：第二個(gè)for循環(huán)中循環(huán)的次數(shù)要建立在numsSize的基礎(chǔ)上再加1，因?yàn)槭侨鄙倭艘粋€(gè)數(shù)字，所以理論上數(shù)組的長度是在原基礎(chǔ)上加1的。

題二：（旋轉(zhuǎn)數(shù)組）

鏈接：https://leetcode-cn.com/problems/rotate-array/

 此題的進(jìn)階思想中就明確了使用空間復(fù)雜度為O(1)的算法來解決此問題，正文開始

法一：右旋K次，一次移動(dòng)一個(gè)

思想：

首先，定義一個(gè)變量tmp把數(shù)組的最后一個(gè)元素保存起來。其次，把前N-1個(gè)值往后挪。最后，把tmp的值放到第一個(gè)位置。如圖所示：

此法時(shí)間復(fù)雜度為：O(N*K)，空間復(fù)雜度O(1)，此法的空間復(fù)雜度滿足題意了，但有個(gè)風(fēng)險(xiǎn)，就是當(dāng)K%N=N-1時(shí)時(shí)間復(fù)雜度過大，為O(N^2)，所以再看看有無更好方法：

法二： 額外開數(shù)組

思想：

 額外開辟一個(gè)新數(shù)組，把后K個(gè)元素放到新數(shù)組前面，再把原數(shù)組N-K個(gè)元素拷貝到新數(shù)組后面。但是此法的時(shí)間復(fù)雜度是O(N)，空間復(fù)雜度也是O(N)，不符合題意，再換：

法三：三趟逆置

思想：

第一趟對它的前N-K個(gè)元素逆置，第二趟對它的后K個(gè)元素逆置，最后整體逆置。如圖所示：

此法非常巧妙，時(shí)間復(fù)雜度O(N)，空間復(fù)雜度O(N)，符合題意

代碼如下：

void reverse(int*nums,int left,int right)
{
    while(left<right)
    {
        int tmp=nums[left];
        nums[left]=nums[right];
        nums[right]=tmp;
        left++;
        right--;
    }
}
void rotate(int* nums, int numsSize, int k){
    k%=numsSize;
    reverse(nums,0,numsSize-k-1);
    reverse(nums,numsSize-k,numsSize-1);
    reverse(nums,0,numsSize-1);
}

 注意：這里當(dāng)k=7時(shí)，相當(dāng)于全部逆置完了一遍，也就是又回到了原來的樣子，是有規(guī)律可循的，所以真正逆置的次數(shù)為k%=numsSize;

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

最新評論