C語言演演算法的時間複雜度和空間複雜度

2022-07-08 14:03:40

1.演演算法效率

1.1 如何衡量一個演演算法的好壞

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

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

斐波那契數列的遞迴實現方式非常簡潔，但簡潔一定好嗎？那該如何衡量其好與壞呢？

1.2演演算法的複雜度

演演算法在編寫成可執行程式後，執行時需要耗費時間資源和空間(記憶體)資源。因此衡量一個演演算法的好壞，一般是從時間和空間兩個維度來衡量的，即時間複雜度和空間複雜度。

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

2.時間複雜度

2.1 時間複雜度的概念

時間複雜度的定義：在電腦科學中，演演算法的時間複雜度是一個函數，它定量描述了該演演算法的執行時間。一個演演算法執行所耗費的時間，從理論上說，是不能算出來的，只有你把你的程式放在機器上跑起來，才能知道。但是我們需要每個演演算法都上機測試嗎？是可以都上機測試，但是這很麻煩，所以才有了時間複雜度這個分析方式。一個演演算法所花費的時間與其中語句的執行次數成正比例，演演算法中的基本操作的執行次數，為演演算法的時間複雜度。

即：找到某條基本語句與問題規模N之間的數學表示式，就是算出了該演演算法的時間複雜度。

下面舉個例子：

請計算一下Func1中++count語句總共執行了多少次？

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^2 + 2*N + 10

代入數位計算一下：

N = 10 F(N) = 130
N = 100 F(N) = 10210
N = 1000 F(N) = 1002010

可以發現當N越來越大的時候，數位的大小主要取決於N^2了。

實際中我們計算時間複雜度時，我們其實並不一定要計算精確的執行次數，而只需要大概執行次數，那麼這裡我們使用大O的漸進表示法。

2.2 大O的漸進表示法

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

推導大O階方法：

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

使用大O的漸進表示法以後，Func1的時間複雜度為： O(N^2)

N = 10 F(N) = 100
N = 100 F(N) = 10000
N = 1000 F(N) = 1000000

通過上面我們會發現大O的漸進表示法去掉了那些對結果影響不大的項，簡潔明瞭的表示出了執行次數。

另外有些演演算法的時間複雜度存在最好、平均和最壞情況：

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

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

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

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

2.3常見時間複雜度計算舉例

範例1

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

基本操作執行了2*N + 10次，而通過推導大O階方法

用常數1取代加法常數，得到2*N + 1

只保留最高階項，得到2*N

將最高階項的係數變為1，得到N

所以最後的時間複雜度是O(N)

範例2：計算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(N+M)

範例3：計算Func4的時間複雜度

void Func4(int N)
{
	int count = 0;
	for (int k = 0; k < 100; ++k)
	{
		++count;
	}
	printf("%dn", count);
}

用常數1替代100，時間複雜度是O(1)

範例4：計算strchr的時間複雜度

const char* strchr(const char* str, int character)
{
	while (*str != character)
	{
		str++;
	}
	return str;
}

最快執行了1次，最慢執行了N次，所以時間複雜度是O(N)

範例5：計算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;
	}
}

第一趟氣泡排序了N - 1次，第二趟氣泡排序了N - 2次，依次類推，排序這個基本操作在最壞的情況下一共執行了(N*(N+1)/2次，而最好的情況下是陣列已經排好了，此時只需要執行N次，時間複雜度取最壞的情況，所以是O(N^2)

範例6：計算BinarySearch的時間複雜度

int BinarySearch(int* a, int n, int x)
{
	assert(a);
	int begin = 0;
	int end = n - 1;
	// [begin, end]：begin和end是左閉右閉區間，因此有=號
	while (begin <= end)
	{
		int mid = begin + ((end - begin) >> 1);
		if (a[mid] < x)
			begin = mid + 1;
		else if (a[mid] > x)
			end = mid - 1;
		else
			return mid;
	}
	return -1;
}

假如有序陣列有N個數，那麼查詢一次就會將陣列的範圍縮小一半，直到最後只剩下一個數

可以這麼用數位表示：

N / 2 / 2 / 2 / 2 / 2 / 2 ...... / 2 / 2 = 1

假設查詢了x次，也就是每次將陣列縮小一半(除以2)這個基本操作執行了x次，那麼這個x與N之間的關係是2^x = N

那麼x = logN，這裡預設底數為2

所以時間複雜度是O(logN)

範例7：計算階乘遞迴Fac的時間複雜度

long long Fac(size_t N)
{
	if (0 == N)
		return 1;
	return Fac(N - 1) * N;
}

基本操作遞迴了N次，所以時間複雜度為O(N)

範例8：計算斐波那契遞迴Fib的時間複雜度

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

基本操作遞迴了約為2^N次，根據推到大O階的方法，所以最後的時間複雜度為O(N)

3.空間複雜度

空間複雜度也是一個數學表示式，是對一個演演算法在執行過程中臨時佔用儲存空間大小的量度

空間複雜度不是程式佔用了多少bytes的空間，因為這個也沒太大意義，所以空間複雜度算的是變數的個數。空間複雜度計算規則基本跟實踐複雜度類似，也使用大O漸進表示法。

注意：函數執行時所需要的棧空間(儲存引數、區域性變數、一些暫存器資訊等)在編譯期間已經確定好了，因此空間複雜度主要通過函數在執行時候顯式申請的額外空間來確定。

範例1：計算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;
	}
}

可見，紅框標註的地方，是在函數的內部額外建立了4個變數，也就是開闢了常數個額外空間，所以空間複雜度為O(1)

範例2：計算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;
}

在動態記憶體中開闢了N+1個sizeof(long long)大小的空間，所以空間複雜度為O(N)

範例3：計算階乘遞迴Fac的空間複雜度

long long Fac(size_t N)
{
	if (N == 0)
		return 1;
	return Fac(N - 1) * N;
}

遞迴呼叫了N次，開闢了N個棧幀，每個棧幀使用了常數個空間，所以空間複雜度為O(N)

範例4：計算Fibonacci的空間複雜度

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

每一次遞迴呼叫時，每兩個子函數用的函數棧幀空間都是同一個，所以只額外開闢了N個棧幀，空間複雜度為O(N)

4.常見覆雜度對比

5.複雜度的OJ練習

5.1消失的數位OJ

連結：//img.jbzj.com/file_images/article/202207/202207081035315

題目描述：陣列nums包含從0到n的所有整數，但其中缺了一個。請編寫程式碼找出那個缺失的整數。你有辦法在O(n)時間內完成嗎？

範例 1：

輸入：[3,0,1]
輸出：2

範例 2：

輸入：[9,6,4,2,3,5,7,0,1]
輸出：8

這裡給出時間複雜度都為O(N)的思路

1.建立一個大小為N + 1的陣列，然後用-1將陣列初始化，再將題目中給定陣列中的數位放到新建立陣列中對應下標的位置，最後將新陣列中的數位遍歷一遍，找出-1所對應的下標，該下標的數位就是所要找的消失的數位了。
2.將題目給定陣列中的數位全都互斥或一次，再與從0到N+1的數位全部互斥或一次，就可以得到那個消失的數位了，其思路類似於在一個陣列中尋找單身狗。
3.將題目給定陣列進行快速排序，而後進行二分查詢，找不到的那個數位即為要找的數位了。
4.將N+1個數位進行全都加起來，然後減去題目給定陣列中的N個數位，最後得到的數位就是要找的消失的數位了。

3.2 旋轉陣列OJ

連結：//img.jbzj.com/file_images/article/202207/202207081035316

題目描述：給你一個陣列，將陣列中的元素向右輪轉 k 個位置，其中 k 是非負數。

範例 1:

輸入: nums = [1,2,3,4,5,6,7], k = 3
輸出: [5,6,7,1,2,3,4]
解釋:
向右輪轉 1 步: [7,1,2,3,4,5,6]
向右輪轉 2 步: [6,7,1,2,3,4,5]
向右輪轉 3 步: [5,6,7,1,2,3,4]

範例 2:

輸入：nums = [-1,-100,3,99], k = 2
輸出：[3,99,-1,-100]
解釋:
向右輪轉 1 步: [99,-1,-100,3]
向右輪轉 2 步: [3,99,-1,-100]

這裡給出3種思路：

1.將最後一個數用一個臨時變數儲存起來，然後將陣列中前面的數依次往後挪動，最後將臨時變數中的數放到陣列的第一個位置，這樣的操作迴圈k次，最壞的情況下是k=N-1，這時時間複雜度是O(N^2)，而空間複雜度是O(1)，因為只開闢了1個臨時變數，並且這個變數的空間是重複利用的。
2.額外開闢一個同樣大小的陣列，然後按照k的大小擷取資料依次放入陣列中，這種做法的時間複雜度為O(N)，空間複雜度為O(N)，這是以空間來換時間的做法。
3.根據k的大小將陣列分位2個部分，第1個部分和第2個部分分別自旋，最後再將整個陣列自旋一次，由於旋轉交換的過程中只開闢了一個臨時變數的空間，所以空間複雜度為O(1)，時間複雜度為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 - 1 - k);
    reverse(nums, numsSize - k, numsSize - 1);
    reverse(nums, 0, numsSize - 1);
}

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