以此算法為例，count++,執(zhí)行次數(shù)為x*x次，那么它的時間復雜度為O(x^2)

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

此例中運行最多的代碼段為++count，可以看出來它的執(zhí)行次數(shù)為

F(n)=n*n+2*n+10；應用大O的漸進表示法，我們保留最高階n*n=n^2,因此上述算法的時間復雜度為O(n^2)。

那么為什么是這樣呢？因為當n無窮大時，除去最高階對整個影響較大外，其他的常數(shù)及一次項對整體次數(shù)來說可忽略不計，時間復雜度取的是最差結(jié)果，因此對時間復雜度有了大O的漸進表示法。

4.空間復雜度

定義

空間復雜度也是一個數(shù)學表達式，不是程序占用了多少字節(jié)的空間，而是對一個算法在運行過程中臨時占用存儲空間大小的量度 。

空間復雜度計算規(guī)則基本跟實踐復雜度類似，也使用大O漸進表示法。
注意：函數(shù)運行時所需要的棧空間(存儲參數(shù)、局部變量、一些寄存器信息等)在編譯期間已經(jīng)確定好了，因此空間復雜度主要通過函數(shù)在運行時候顯式申請的額外空間來確定。

舉例：

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，exchange，i 在運行時要申請額外的空間來完成程序，因此額外申請了3個空間，是常數(shù)，因此用大O漸進表示法表示其空間復雜度就是O(1)

?5.時間復雜度和空間復雜度的對比

注：時間是累加的，一去不復返的；空間卻是可以循環(huán)利用的。

?這里我們用斐波那契數(shù)的遞歸算法來對比時間復雜度與空間復雜度