1.算法效率

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

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

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

斐波那契數(shù)列的遞歸實現(xiàn)方式非常簡潔，但簡潔一定好嗎？那該如何衡量其好與壞呢？

1.2算法的復雜度

算法在編寫成可執(zhí)行程序后，運行時需要耗費時間資源和空間(內存)資源 。因此衡量一個算法的好壞，一般是從時間和空間兩個維度來衡量的，即時間復雜度和空間復雜度。

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

2.時間復雜度

2.1 時間復雜度的概念

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

即：找到某條基本語句與問題規(guī)模N之間的數(shù)學表達式，就是算出了該算法的時間復雜度。 

下面舉個例子：

請計算一下Func1中++count語句總共執(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);
}

 Func1 執(zhí)行的基本操作次數(shù) ： F(N) = N^2 + 2*N + 10

代入數(shù)字計算一下：

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

可以發(fā)現(xiàn)當N越來越大的時候，數(shù)字的大小主要取決于N^2了。

實際中我們計算時間復雜度時，我們其實并不一定要計算精確的執(zhí)行次數(shù)，而只需要大概執(zhí)行次數(shù)，那么這里我們使用大O的漸進表示法。

2.2 大O的漸進表示法

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

推導大O階方法：

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

使用大O的漸進表示法以后，F(xiàn)unc1的時間復雜度為： O(N^2)

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

通過上面我們會發(fā)現(xiàn)大O的漸進表示法去掉了那些對結果影響不大的項，簡潔明了的表示出了執(zhí)行次數(shù)。

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

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

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

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

在實際中一般情況關注的是算法的最壞運行情況，所以數(shù)組中搜索數(shù)據(jù)時間復雜度為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("%d\n", count);
}

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

用常數(shù)1取代加法常數(shù)，得到2*N + 1

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

將最高階項的系數(shù)變?yōu)?，得到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("%d\n", count);
}

時間復雜度為O(N+M)

實例3：計算Func4的時間復雜度

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

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

實例4：計算strchr的時間復雜度

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

最快執(zhí)行了1次，最慢執(zhí)行了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次，依次類推，排序這個基本操作在最壞的情況下一共執(zhí)行了(N*(N+1)/2次，而最好的情況下是數(shù)組已經(jīng)排好了，此時只需要執(zhí)行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是左閉右閉區(qū)間，因此有=號
	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;
}

假如有序數(shù)組有N個數(shù)，那么查找一次就會將數(shù)組的范圍縮小一半，直到最后只剩下一個數(shù)

可以這么用數(shù)字表示：

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

假設查找了x次，也就是每次將數(shù)組縮小一半(除以2)這個基本操作執(zhí)行了x次，那么這個x與N之間的關系是2^x = N

那么x = logN，這里默認底數(shù)為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次，根據(jù)推到大O階的方法，所以最后的時間復雜度為O(N)

3.空間復雜度

空間復雜度也是一個數(shù)學表達式，是對一個算法在運行過程中臨時占用存儲空間大小的量度

空間復雜度不是程序占用了多少bytes的空間，因為這個也沒太大意義，所以空間復雜度算的是變量的個數(shù)。空間復雜度計算規(guī)則基本跟實踐復雜度類似，也使用大O漸進表示法。

注意：函數(shù)運行時所需要的?？臻g(存儲參數(shù)、局部變量、一些寄存器信息等)在編譯期間已經(jīng)確定好了，因此空間復雜度主要通過函數(shù)在運行時候顯式申請的額外空間來確定。

實例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;
	}
}

可見，紅框標注的地方，是在函數(shù)的內部額外創(chuàng)建了4個變量，也就是開辟了常數(shù)個額外空間，所以空間復雜度為O(1)

實例2：計算Fibonacci的空間復雜度

// 返回斐波那契數(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;
}

 在動態(tài)內存中開辟了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個棧幀，每個棧幀使用了常數(shù)個空間，所以空間復雜度為O(N)

實例4：計算Fibonacci的空間復雜度

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

每一次遞歸調用時，每兩個子函數(shù)用的函數(shù)棧幀空間都是同一個，所以只額外開辟了N個棧幀，空間復雜度為O(N)

4.常見復雜度對比

5.復雜度的OJ練習

5.1消失的數(shù)字OJ

鏈接：//img.jbzj.com/file_images/article/202207/202207081035315

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

示例 1：

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

示例 2：

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

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

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

3.2 旋轉數(shù)組OJ

鏈接：//img.jbzj.com/file_images/article/202207/202207081035316

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

示例 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.將最后一個數(shù)用一個臨時變量保存起來，然后將數(shù)組中前面的數(shù)依次往后挪動，最后將臨時變量中的數(shù)放到數(shù)組的第一個位置，這樣的操作循環(huán)k次，最壞的情況下是k=N-1，這時時間復雜度是O(N^2)，而空間復雜度是O(1)，因為只開辟了1個臨時變量，并且這個變量的空間是重復利用的。
• 2.額外開辟一個同樣大小的數(shù)組，然后按照k的大小截取數(shù)據(jù)依次放入數(shù)組中，這種做法的時間復雜度為O(N)，空間復雜度為O(N)，這是以空間來換時間的做法。
• 3.根據(jù)k的大小將數(shù)組分位2個部分，第1個部分和第2個部分分別自旋，最后再將整個數(shù)組自旋一次，由于旋轉交換的過程中只開辟了一個臨時變量的空間，所以空間復雜度為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語言時間復雜度內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論