C語言 詳細解析時間複雜度與空間複雜度

一、概念

1.1、演演算法效率

如何衡量一個演演算法的好壞?比如對於以下斐波那契數列：

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

斐波那契數列用遞迴實現方式非常簡潔，但簡潔一定好嗎？那該如何衡量其好與壞呢？在學完時間複雜度會為您揭曉。

演演算法效率分析分為兩種：第一種是時間效率，第二種是空間效率。時間效率被稱為時間複雜度，而空間效率被稱作空間複雜度。 時間複雜度主要衡量的是一個演演算法的執行速度，而空間複雜度主要衡量一個演演算法所需要的額外空間，在計算機發展的早期，計算機的儲存容量很小。所以對空間複雜度很是在乎。但是經過計算機行業的迅速發展，計算機的儲存容量已經達到了很高的程度。所以我們如今已經不需要再特別關注一個演演算法的空間複雜度

1.2、時間複雜度

一個演演算法所花費的時間與其中語句的執行次數成正比例，演演算法中的基本操作的執行次數，為演演算法的時間複雜度。

1.3、空間複雜度

空間複雜度是對一個演演算法在執行過程中臨時佔用儲存空間大小的量度 。空間複雜度不是程式佔用了多少bytes的空間，因為這個也沒太大意義，所以空間複雜度算的是變數的個數。空間複雜度計算規則基本跟實踐複雜度類似，也使用大O漸進表示法。

二、計算

2.1、大O的漸進表示法

先看一串程式碼：

// 請計算一下Func1基本操作執行了多少次？
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("%dn", count);
}

演演算法中的基本操作的執行次數，為演演算法的時間複雜度。顯而易見，這裡Func1 執行的最準確操作次數 ：F(N)=N*N+2*N+10

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

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

實際中我們計算時間複雜度時，我們其實並不一定要計算精確的執行次數，而只需要大概執行次

數，那麼這裡我們使用大O的漸進表示法。，因而上題的時間複雜度為O(N^2)

大O符號（Big O notation）：是用於描述函數漸進行為的數學符號。

推導大O階方法：

• 用常數1取代執行時間中的所有加法常數。
• 在修改後的執行次數函數中，只保留最高階項。
• 如果最高階項存在且不是1，則去除與這個專案相乘的常數。得到的結果就是大O階。

通過上面我們會發現大O的漸進表示法去掉了那些對結果影響不大的項，簡潔明瞭的表示出了執行次數。另外有些演演算法的時間複雜度存在最好、平均和最壞情況：

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

例如：在一個長度為N陣列中搜尋一個資料x

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

在實際中一般情況關注的是演演算法的最壞執行情況，所以陣列中搜尋資料時間複雜度為O(N)

注意：遞迴演演算法時間複雜度計算

• 每次函數呼叫是O(1)，那麼就看他的遞迴次數
• 每次函數呼叫不是O(1)，那麼就看他的遞迴呼叫中次數的累加

2.2、時間複雜度計算

例題：

例一：

// 計算Func2的時間複雜度？
void Func2(int N)
{
	int count = 0;
	for (int k = 0; k < 2 * N; ++k)
	{
		++count;
	}
	int M = 10;
	while (M--)
	{
		++count;
	}
	printf("%dn", count);
}

答案：O(N)

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

例二：

// 計算Func3的時間複雜度？
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("%dn", count);
}

答案：O(M+N)

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

例三：

// 計算Func4的時間複雜度？
void Func4(int N)
{
	int count = 0;
	for (int k = 0; k < 100; ++k)
	{
		++count;
	}
	printf("%dn", count);
}

答案：O(1)

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

例四：

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

答案：O(N)

解析：此題就要分情況了，這裡假設字串為abcdefghijklmn，如果目標字元找的是g，則需要執行N/2次，如果找到是a，則需要執行1次，如果找n，則N次，所以要分情況，這裡就出現了有些演演算法的時間複雜度存在最好O(1)、平均O(N/2)和最壞O(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;
	}
}

答案：O(N^2)

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

例六：

// 計算BinarySearch的時間複雜度？
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)

解析：此題很明顯考到的是二分查詢。假設陣列長度為N，且找了X次，則1*2*2*2*2*……*2=N，即為2^X=N，則X等於log以2為底N的對數，而演演算法的複雜度計算，喜歡省略簡寫成logN，因為很多地方不好寫底數，所以此題時間複雜度為O(logN)

例七：

// 計算階乘遞迴Factorial的時間複雜度？
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);
}

這串程式碼是上文最開始呈現的程式碼，程式碼風格十分簡單，短短几行便可完成斐波那契數列的計算，可看似這麼簡潔的程式碼真的“好”嗎？先來計算一下時間複雜度：

答案：O(2^N)

解析：

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

但是，根據2^N這個時間複雜度是個非常大的數位，當n=10時，在VS環境下很快容易得到答案，但是當n稍微再大一點比如說是50，就要等上很長一段時間才能將結果算出來，由此可見，簡潔的程式碼不一定是最優的程式碼。

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

複雜度對比：

2.3、空間複雜度計算

• 空間複雜度也是一個數學表示式，是對一個演演算法在執行過程中臨時佔用儲存空間大小的量度 。空間複雜度不是程式佔用了多少bytes的空間，因為這個也沒太大意義，所以空間複雜度算的是變數的個數。
• 空間複雜度計算規則基本跟實踐複雜度類似，也使用大O漸進表示法。
• 注意：函數執行時所需要的棧空間(儲存引數、區域性變數、一些暫存器資訊等)在編譯期間已經確定好了，因此空間複雜度主要通過函數在執行時候顯式申請的額外空間來確定。

例題

例一：

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

答案：O(1)

解析：這裡其實總共開闢了三個空間，分別為end、exchange、i，既然是常數個變數，那麼空間複雜度就是O(1)，空間複雜度算的是申請的額外空間，所以跟上面的int*a和int n沒有關係。可能有人覺著這是個for迴圈，exchange應該開闢n次，其實每次迴圈進來，exchange都會重新開闢，結束一次迴圈exchange銷燬，以此類推，exchange始終是同一個空間。

而什麼時候會出現O(n)呢？

1、malloc一個陣列

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

此情況的前提是numsSize必須是個未知的數位，如果是具體數位，那麼空間複雜度依舊是O(1)

2、變長陣列

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

例二：

// 計算Fibonacci的空間複雜度？
// 返回斐波那契數列的前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型別的陣列，看到這就不需要再過多計較後續建立了幾個變數，因為空間複雜度是估算，所以直接就是O(N)

例三：

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

答案：O(1)

解析： 這裡遞迴函數是要建立棧幀的，而建立棧幀的個數為N個，每個棧幀的變數都是常數個，N個即空間複雜度為O(N)

例四：

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

答案：O(N)

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

三、有複雜度要求的習題

題一：（消失的數位）

連結：https://leetcode-cn.com/problems/missing-number-lcci/

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

法一：相加 - 相加

思想：

此題是在一串連續的整數中缺了一個數，那我們就把理應有的整數個數依次相加再減去原陣列中缺一個數位的所有元素和即為我們想要的數位。

程式碼如下：

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，這裡假設一共有10個數位，那麼這裡nums陣列就是 [ 0 - 9 ]，不過其中缺了一個數位，我們已經深知互斥或的運算規則（相同為0，相異為1）以及兩個重要結論：1、兩個相同的數位互斥或等於0。2、0與任何數位互斥或等於該任意數位。因此，我們完全可以先把原陣列的所有元素互斥或起來，再把理論上0-n依次遞增的所有元素都互斥或起來，然後兩塊再次互斥或得到的就是缺少的數位。

畫圖展示：

 程式碼如下：

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迴圈中迴圈的次數要建立在numsSize的基礎上再加1，因為是缺少了一個數位，所以理論上陣列的長度是在原基礎上加1的。

題二：（旋轉陣列）

連結：https://leetcode-cn.com/problems/rotate-array/

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

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

思想：

首先，定義一個變數tmp把陣列的最後一個元素儲存起來。其次，把前N-1個值往後挪。最後，把tmp的值放到第一個位置。如圖所示：

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

法二： 額外開陣列

思想：

 額外開闢一個新陣列，把後K個元素放到新陣列前面，再把原陣列N-K個元素拷貝到新陣列後面。但是此法的時間複雜度是O(N)，空間複雜度也是O(N)，不符合題意，再換：

法三：三趟逆置

思想：

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

此法非常巧妙，時間複雜度O(N)，空間複雜度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時，相當於全部逆置完了一遍，也就是又回到了原來的樣子，是有規律可循的，所以真正逆置的次數為k%=numsSize;

到此這篇關於C語言 詳細解析時間複雜度與空間複雜度的文章就介紹到這了,更多相關C語言 時間複雜度 內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！