一、概念

1.1、算法效率

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

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

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

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

1.2、時間復(fù)雜度

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

1.3、空間復(fù)雜度

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

二、計算

2.1、大O的漸進表示法

先看一串代碼：

// 請計算一下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ù)，為算法的時間復(fù)雜度。顯而易見，這里Func1 執(zhí)行的最準確操作次數(shù) ：F(N)=N*N+2*N+10

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2、時間復(fù)雜度計算

例題：

例一：

// 計算Func2的時間復(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)

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

例二：

// 計算Func3的時間復(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)

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

例三：

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

答案：O(1)

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

例四：

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

答案：O(N)

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

例五：

// 計算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(N^2)

解析：此段代碼考到的是冒泡排序。第一趟的冒泡排序走了N次，第二趟走了N-1次，第三趟N-2，……最后就是1，次規(guī)律正合等差數(shù)列，求和即為(N+1)*N/2，當然這個是最準確的，這里還要找對結(jié)果影響最大的那一項，即N^2，所以時間復(fù)雜度是O(N^2)

例六：

// 計算BinarySearch的時間復(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ù)雜度計算，喜歡省略簡寫成logN，因為很多地方不好寫底數(shù)，所以此題時間復(fù)雜度為O(logN)

例七：

// 計算階乘遞歸Factorial的時間復(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)的代碼，代碼風格十分簡單，短短幾行便可完成斐波那契數(shù)列的計算，可看似這么簡潔的代碼真的“好”嗎？先來計算一下時間復(fù)雜度：

答案：O(2^N)

解析：

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

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

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

復(fù)雜度對比：

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

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

例題

例一：

// 計算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)

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

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

1、malloc一個數(shù)組

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

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

2、變長數(shù)組

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

例二：

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

答案：O(N+1)

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

例三：

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

答案：O(1)

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

例四：

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

答案：O(N)

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

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

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

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

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

法一：相加 - 相加

思想：

此題是在一串連續(xù)的整數(shù)中缺了一個數(shù)，那我們就把理應(yīng)有的整數(shù)個數(shù)依次相加再減去原數(shù)組中缺一個數(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個數(shù)字，那么這里nums數(shù)組就是 [ 0 - 9 ]，不過其中缺了一個數(shù)字，我們已經(jīng)深知異或的運算規(guī)則（相同為0，相異為1）以及兩個重要結(jié)論：1、兩個相同的數(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;
}

注意：第二個for循環(huán)中循環(huán)的次數(shù)要建立在numsSize的基礎(chǔ)上再加1，因為是缺少了一個數(shù)字，所以理論上數(shù)組的長度是在原基礎(chǔ)上加1的。

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

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

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

法一：右旋K次，一次移動一個

思想：

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

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

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

思想：

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

法三：三趟逆置

思想：

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

此法非常巧妙，時間復(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);
}

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

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

最新評論