一、時間復雜度

1）O(n)的含義

• 程序消耗的時間用算法的操作單元數來表示
• 假設數據的規(guī)模為n，則用f(n)表示操作單元數的大小，而f(n)常被簡化
• O表示的是一般的情況，而不是上界或下界。并且它是在數據量級非常大的情況下所展現(xiàn)出的時間復雜度
• 因為O代表的是一個一般的情況，所以當用例不同時，算法的時間復雜度不同，需要具體分析

2）復雜表達式的簡化

表達式簡化遵循以下兩個原則：

• 去掉常數項
• 只保留最高項

為例分析：

• 去掉常數項后為
• 只保留最高項后為

不難想象，當n趨一個非常大的數量級的時候，最高項將其決定性作用。但是若常數項也是一個非常大的數量級，那我們就不可以輕易將其舍去。

3）O(n)不一定優(yōu)于O(n^2)

????????由上面簡化法則我們可以看到，常數項是被忽略的，如與，當n < 20時前者的操作單位數是小于后者的。

所以在決定使用什么算法的時候并不是算法的時間復雜度越低越好，還需要考慮數據的規(guī)模

????????那為什么我們默認時間復雜度低于呢？正如前面提到的關于O的定義：它是在數據量級非常大的情況下所展現(xiàn)出的時間復雜度，所以我們默認前者的時間復雜度更優(yōu)。

?4）遞歸的時間復雜度

?遞歸的時間復雜度 = 遞歸次數 X 每次遞歸的操作次數。

現(xiàn)在我們從一道面試題來分析時間復雜度：求x的n次方

①直觀的for循環(huán)遍歷

int fuc1(int n)
{
	int ret = 1;
	for (int i = 1; i < n; i++)
		ret *= i;
	return ret;
}

【分析】時間復雜度為O(n)，因為操作單元數為n次?

②遞歸版本1

int fuc2(int n,int x)
{
	if (n == 0)
		return 1;
	if (n == 1)
		return x;
	return x * fuc2(n - 1, x);
}

【分析】遞歸次數為n次，每次相乘的時間復雜度為O(1)，所以時間復雜度仍為O(n)

?③遞歸版本2?

int fuc3(int n, int x)
{
	if (n == 0)
		return 1;
	if (n == 1)
		return x;
	if (n % 2 == 1)
		return fuc3(n / 2, x) * fuc3(n / 2, x) * x;//奇數次冪的情況
	return fuc3(n / 2, x) * fuc3(n / 2, x);		   //偶數次冪的情況
}

【分析】上面代碼的時間復雜度為嗎？我們可以畫二叉樹來理解，以n = 16為例?

每一個結點都表示需要進行一次遞歸，因此結點數代表著遞歸次數，所以先我們計算二叉樹結點數?

• 一顆滿二叉樹的結點數根據等比數列求和公式可以求出為：?（m為二叉樹深度）?
• 二叉樹深度m 計算公式?：（向下取整）?

????????因為n為奇數時我們將其拆成偶數處理，如：

將深度公式代入結點總和公式我們可以得出， 節(jié)點數 = n - a（a為某個常數），所以時間復雜度還是

④遞歸版本3?

int fuc4(int n, int x)
{
	if (n == 0)
		return 1;
	else if (n == 1)
		return 1;
	int t = fuc4(n / 2, x);
	if (n % 2 == 1)
		return t * t * x;
	return t * t;
}

通過將遞歸操作抽離出來從而減少遞歸次數，我們真正實現(xiàn)了時間復雜度為?

我們再分析一下求斐波那契數列函遞歸解法時間復雜度：?

int fib(int n)
{
	if (n <= 0)
		return 1;
	if (n == 1)
		return 1;
	return fib(n - 1) + fib(n - 2);
}

同樣的我們可以畫二叉樹來分析。求第k個斐波那契數，我們不難想象，我們將構造出一個深度為k的二叉樹，深度為k的二叉樹最多有個結點，所以我們得出該算法的時間復雜度為。優(yōu)化的思路和上述求x的n次方的思路一樣，主要是減少遞歸的調用次數?

int fib(int first, int second, int n)
{
	if (n <= 0)
		return 0;
	if (n < 3)
		return 1;
	else if (n == 3)
		return first + second;
	else
		return fib(second, first + second, n - 1);
}

二、空間復雜度

1）O(1)空間復雜度?

程序占用空間不隨n的變化而變化，即占用的空間是一個常數?

for(int j = 0; j < n; j++)
{
	j++;
}

程序占用的空間與n無關，上圖中之涉及為j分配內存空間，是一個固定的常量?

2）???????O(n)空間復雜度?

程序占用空間隨n增長而線性增長；?

int arr[n];

3）???????O(mn)空間?復雜度?

常常是定義一個二維集合，集合的大小與集合的長與寬相管?

int arr[row * col];

4）遞歸算法空間算法復雜度分析?

?遞歸算法空間復雜度 = 每次遞歸的空間復雜度 X 遞歸深度（遞歸調用棧的最大長度）

我們同樣來分析上面提到的求斐波那契數函數的空間復雜度：?

int f(int n)
{
	if (n <= 0)
		return 1;
	if (n == 1)
		return 1;
	return f(n - 1) + f(n - 2);
}

在遞歸的過程中依次將f(5)，f(4)， f(3)，f(2)，f(1)壓棧，每一次調用所占用的空間都為所以占用的空間為，所以上述代碼的空間復雜度為?

我們再來分析遞歸實現(xiàn)的二分查找的空間復雜度?：

int binary_search(int arr[], int l, int r, int x)
{
	if (r >= l)
	{
		int mid = l + (r - l) / 2; //避免先加后除產生溢出的錯誤
		if (arr[mid] == x)
			return mid;
		else if (arr[mid] < x)
			return binary_search(arr, mid + 1, r ,x);
		else
			return binary_search(arr, l, mid - 1, x);
	}
	return -1;
}

每次遞歸所占用的空間都是一定的，所以每次遞歸的空間復雜度為，而遞歸的最大深度為，所以空間復雜度為