一、時間復雜度

時間復雜度：一個算法所花費的時間與其中語句的執行次數成正比例，算法中的基本操作的執行次數。

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

舉個例子：

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 執行的基本操作次數 ：$N^2$$+2N+10$

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

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

?注意：算法的時間復雜度存在最好、平均和最壞情況：
① 最壞情況：任意輸入規模的最大運行次數(上界)
② 平均情況：任意輸入規模的期望運行次數(期望對標概率論中的期望)
③ 最好情況：任意輸入規模的最小運行次數(下界)

在實際中一般情況關注的是算法的最壞運行情況

大O法的規則：

1. 結果只保留最高階項，且去掉系數
2. 結果若為常數,記為 $O(1)$

例題

例一：

//計算Func2的時間復雜度？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 執行的基本操作次數 ：$2N+10$
用大$O$法表示：$O(N)$

例二：

// 計算Func3的時間復雜度？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 執行的基本操作次數 ：$M+N$
用大$O$法表示：$O(M+N)$

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

例三：

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

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

例四：

// 計算strchr的時間復雜度？const char * strchr ( const char * str, int character );

?strchr函數的用法
考慮最壞的情況，用大$O$法表示：$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]);//第一輪N次，最后一輪1次，三角形面積計算得(N+1)*N/2				exchange = 1;			}		}		if (exchange == 0)			break;	}}

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

例六：

// 計算BinarySearch的時間復雜度？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的思想來看，一半一半的查找容易得： $O(lo{g}_{2}N)$

例七：

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

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

例八：

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

由圖可得執行的基本操作次數大概為 ：$2^N?1$
復雜度為： $O(2^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;	}}

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

例二：

// 計算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$個數組，還有$N?1$個i，因此空間復雜度為：$O(N)$
時間復雜度：$O(N)$

例三：

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

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

例八：

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

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

空間是可以重復利用的，但是時間是累計的。

三、常見復雜度對比

算法復雜度優先級： 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