C語言時間復雜度與空間復雜度實例分析

這篇文章主要介紹“C語言時間復雜度與空間復雜度實例分析”，在日常操作中，相信很多人在C語言時間復雜度與空間復雜度實例分析問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”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("%d\n", 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("%d\n", 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("%d\n", 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("%d\n", count);
}

答案：O(1)

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

例四：

// 計算strchr的時間復雜度？
const char* strchr(const char* str, char character)
{
	while (*str != '\0')
	{
		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)使用的是同一塊空間，充分說明了時間一去不復返，是累積的，空間回收以后是可以重復利用的。

三、有復雜度要求的習題

題一：（消失的數字）

 此題就明確了一個要求：想辦法在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的。

題二：（旋轉數組）

 此題的進階思想中就明確了使用空間復雜度為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語言時間復雜度與空間復雜度實例分析”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！