一、時(shí)間復(fù)雜度

時(shí)間復(fù)雜度：一個(gè)算法所花費(fèi)的時(shí)間與其中語(yǔ)句的執(zhí)行次數(shù)成正比例，算法中的基本操作的執(zhí)行次數(shù)。

• 找到某條基本語(yǔ)句與問(wèn)題規(guī)模N之間的數(shù)學(xué)表達(dá)式，就是算出了該算法的時(shí)間復(fù)雜度。

舉個(gè)例子：

void Func1(int N){	int count = 0;	for (int i = 0; i < N; ++i)	{		for (int j = 0; j < N; ++j)		{			++count;//N*N		}	}	for (int k = 0; k < 2 * N; ++k)	{		++count;//2*N	}	int M = 10;	while (M--)	{		++count;///10	}	printf("%d/n", count);//將上面相加得 N*N+2*N+10}

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

當(dāng)$N\to \infty$時(shí)，按照高數(shù)中${\lim }_{x\to \infty }$ 的思想,Func1基本操作大概次數(shù)為: $N^2$，該方法稱為大O的漸進(jìn)表示法。

大O的漸進(jìn)表示法: 實(shí)際中我們計(jì)算時(shí)間復(fù)雜度時(shí)，我們其實(shí)并不一定要計(jì)算精確的執(zhí)行次數(shù)，而只需要大概執(zhí)行次數(shù)。
大O符號(hào)（Big O notation）：是用于描述函數(shù)漸進(jìn)行為的數(shù)學(xué)符號(hào)。記為： $O(\square )$

?注意：算法的時(shí)間復(fù)雜度存在最好、平均和最壞情況：
① 最壞情況：任意輸入規(guī)模的最大運(yùn)行次數(shù)(上界)
② 平均情況：任意輸入規(guī)模的期望運(yùn)行次數(shù)(期望對(duì)標(biāo)概率論中的期望)
③ 最好情況：任意輸入規(guī)模的最小運(yùn)行次數(shù)(下界)

在實(shí)際中一般情況關(guān)注的是算法的最壞運(yùn)行情況

大O法的規(guī)則：

1. 結(jié)果只保留最高階項(xiàng)，且去掉系數(shù)
2. 結(jié)果若為常數(shù),記為 $O(1)$

例題

例一：

//計(jì)算Func2的時(shí)間復(fù)雜度？void Func2(int N){	int count = 0;	for (int k = 0; k < 2 * N; ++k)	{		++count;//2 * N	}	int M = 10;	while (M--)	{		++count;//10	}	printf("%d/n", count);}

Func2 執(zhí)行的基本操作次數(shù) ：$2N+10$
用大$O$法表示：$O(N)$

例二：

// 計(jì)算Func3的時(shí)間復(fù)雜度？void Func3(int N, int M){	int count = 0;	for (int k = 0; k < M; ++k)	{		++count;//M	}	for (int k = 0; k < N; ++k)	{		++count;//N	}	printf("%d/n", count);}

Func3 執(zhí)行的基本操作次數(shù) ：$M+N$
用大$O$法表示：$O(M+N)$

? ?情況分析：若$M<<N$,則 $O(N)$
? ?? ?? ? ?? ? ?? ? ?若$M>>N$,則 $O(M)$
? ?? ?? ? ?? ? ?? ? ?若$M\approx N$,則 $O(M)$或$O(N)$

例三：

// 計(jì)算Func4的時(shí)間復(fù)雜度？void Func4(int N){	int count = 0;	for (int k = 0; k < 100; ++k)	{		++count;//100	}	printf("%d/n", count);}

Func4 執(zhí)行的基本操作次數(shù) ：$100$
用大$O$法表示：$O(1)$

例四：

// 計(jì)算strchr的時(shí)間復(fù)雜度？const char * strchr ( const char * str, int character );

?strchr函數(shù)的用法
考慮最壞的情況，用大$O$法表示：$O(N)$

例五：

// 計(jì)算BubbleSort的時(shí)間復(fù)雜度？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]);//第一輪N次，最后一輪1次，三角形面積計(jì)算得(N+1)*N/2				exchange = 1;			}		}		if (exchange == 0)			break;	}}

BubbleSort 執(zhí)行的基本操作次數(shù) ：$(N+1)N/2$
用大$O$法表示：$O(N^2)$

例六：

// 計(jì)算BinarySearch的時(shí)間復(fù)雜度？int BinarySearch(int* a, int n, int x){	assert(a);	int begin = 0;	int end = n - 1;	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;}

從BinarySearch的思想來(lái)看，一半一半的查找容易得： $O(lo{g}_{2}N)$

例七：

// 計(jì)算階乘遞歸Fac的時(shí)間復(fù)雜度？long long Fac(size_t N){	if (0 == N)		return 1;	return Fac(N - 1) * N;}

由圖可得復(fù)雜度為： $O(N)$

例八：

// 計(jì)算斐波那契遞歸Fib的時(shí)間復(fù)雜度？long long Fib(size_t N){	if (N < 3)		return 1;	return Fib(N - 1) + Fib(N - 2);}

由圖可得執(zhí)行的基本操作次數(shù)大概為 ：$2^N?1$
復(fù)雜度為： $O(2^N)$

二、空間復(fù)雜度

空間復(fù)雜度:是對(duì)一個(gè)算法在運(yùn)行過(guò)程中臨時(shí)額外占用存儲(chǔ)空間大小的量度

• 臨時(shí)額外占用的理解：函數(shù)運(yùn)行時(shí)所需要的?？臻g(存儲(chǔ)參數(shù)、局部變量、一些寄存器信息等)在編譯期間已經(jīng)確定好了，因此空間復(fù)雜度主要通過(guò)函數(shù)在運(yùn)行時(shí)候顯式申請(qǐng)的額外空間來(lái)確定

例題

例一：

// 計(jì)算BubbleSort的空間復(fù)雜度？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;	}}

只開(kāi)辟了end和i兩塊空間的大小，因此空間復(fù)雜度為：$O(1)$

例二：

// 計(jì)算Fibonacci的空間復(fù)雜度？// 返回斐波那契數(shù)列的前n項(xiàng)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;}

動(dòng)態(tài)開(kāi)辟了$N+1$個(gè)數(shù)組，還有$N?1$個(gè)i，因此空間復(fù)雜度為：$O(N)$
時(shí)間復(fù)雜度：$O(N)$

例三：

// 計(jì)算階乘遞歸Fac的空間復(fù)雜度？long long Fac(size_t N){	if(N == 0)	return 1;	return Fac(N-1)*N;}

由圖可知空間復(fù)雜度為：$O(N)$

例八：

// 計(jì)算斐波那契遞歸Fib的時(shí)間復(fù)雜度？long long Fib(size_t N){	if (N < 3)		return 1;	return Fib(N - 1) + Fib(N - 2);}

因此空間復(fù)雜度為：$O(N)$

空間是可以重復(fù)利用的，但是時(shí)間是累計(jì)的。

三、常見(jiàn)復(fù)雜度對(duì)比

算法復(fù)雜度優(yōu)先級(jí)： O ( 1 ) > O ( N ) > O ( N l o g N ) > O ( N 2 ) > O ( 2 N ) > O ( N ! ) O(1) >O(N) >O(Nlog^N) >O(N^2) >O(2^N) >O(N!) O(1)>O(N)>O(NlogN)>O(N2)>O(2