目錄

1.本章重點

2.什么是時間復雜度和空間復雜度

2.1演算法效率

2.2時間復雜度的概念

2.3空間復雜度的概念

2.4復雜度計算在演算法中的意義

3.如何計算常見演算法的時間復雜度

3.1大O的漸進表示法

4.如何計算常見演算法的空間復雜度

5.有復雜度要求的演算法題練習

5.1消失的數字

5.2旋轉陣列

1.本章重點

• 什么是時間復雜度和空間復雜度？
• 如何計算常見演算法的時間復雜度和空間復雜度？
• 有復雜度要求的演算法題練習
  

2.什么是時間復雜度和空間復雜度

2.1演算法效率

演算法效率分析分為兩種：第一種是時間效率，第二種是空間效率，

時間效率被稱為時間復雜度，而空間效率被稱作空間復雜度， 時間復雜度主要衡量的是一個演算法的運行速度，而空間復雜度主要衡量一個演算法所需的額外空間，在計算機發展的早期，計算機的存盤容量很小，所以對空間復雜度很是在乎，但是經過計算機行業的迅速發展，計算機的存盤容量已經達到了很高的程度，
所以我們如今已經不需要再特別關注一個演算法的空間復雜度，

2.2時間復雜度的概念

時間復雜度的定義：在計算機科學中，演算法的時間復雜度是一個函式，它定量描述了該演算法的運行時間，一個演算法執行所耗費的時間，從理論上說，是不能算出來的，只有你把你的程式放在機器上跑起來，才能知道（并且在不同條件的硬體下，時間也有所差異），但是我們需要每個演算法都上機測驗嗎？是可以都上機測驗，但是這很麻煩，所以才有了時間復雜度這個分析方式，一個演算法所花費的時間與其中陳述句的執行次數成正比例，演算法中的基本操作的執行次數，為演算法的時間復雜度，

2.3空間復雜度的概念

空間復雜度是對一個演算法在運行程序中臨時占用存盤空間大小的量度 ，空間復雜度不是程式占用了多少bytes的空間，因為這個也沒太大意義，所以空間復雜度算的是變數的個數，空間復雜度計算規則基本跟時間復雜度類似，也使用大O漸進表示法，

2.4復雜度計算在演算法中的意義

小總結：

時間復雜度不算時間，算次數，

空間復雜度不算空間，算變數個數，

3.如何計算常見演算法的時間復雜度

3.1大O的漸進表示法

引子1：時間復雜度O(N^2)

// 計算Func1的時間復雜度？
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);
}

引子2：時間復雜度O(N)

// 計算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);
}

引子3：時間復雜度O(N + M)

// 計算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);
}

解釋：因為我們不知道N和M誰的階大，只能這樣寫，所以也可以得出個結論，大O表示法括號中的未知數不僅僅是1個，也可以是多個，

引子4：時間復雜度O(1)

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

解釋：用常數1取代運行時間中的所有加法常數，

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

大O符號（Big O notation）：是用于描述函式漸進行為的數學符號，

推導大O階方法：

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

使用大O的漸進表示法以后，Func1的時間復雜度為：
N = 10 F(N) = 100
N = 100 F(N) = 10000
N = 1000 F(N) = 1000000

通過上面我們會發現大O的漸進表示法去掉了那些對結果影響不大的項，簡潔明了的表示出了執行次數，
另外有些演算法的時間復雜度存在最好、平均和最壞情況：

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

例如：在一個長度為N陣列中搜索一個資料x

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

在實際中一般情況關注的是演算法的最壞運行情況，所以陣列中搜索資料時間復雜度為O(N)，
舉個例子：（ 取最悲觀的預期 ）

時間復雜度O(N)

//計算strchr的時間復雜度？
const char* strchr(const char* str, char character)
{
	while (*str != '\0')
	{
		if (*str == character)
			return str;
		++str;
	}
	return NULL;
}

解釋：

我們假設字串是“defghsjhsq”，我們想找d，可能一下就找到了O(1)；我們想找q，得需要遍歷到這個字串的最后才能找到；我們想找x，遍歷完了還依舊是沒有找到O(N)，而我們計算時間復雜度是采取最悲觀預期的，所以會采用O(N)，而不是O(1)，

O(1)和O(N)區別：

O(1)意味著：隨著字串變長，時間復雜度是不變的，

O(N)意味著：隨著字串變長，時間復雜度是線性增加的，

計算冒泡排序時間復雜度：時間復雜度O(N^2)

// 計算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;
	}
	return 0;
}

解釋：

計算折半查找時間復雜度：時間復雜度O(log2N)(2是以2為底，可惡的Markdown打不出來)

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

解釋：（ 悟！！ ）

注意：

在演算法的復雜度分析中，因為很多地方不好寫底數，所以我們喜歡省略簡寫成logN（ 表示以2為底數 ），咳咳，在此沒有批評誰的意思，在很多書本中，或者網上資料會寫成O(lgN)來表示以2為底，嚴格來說這樣寫是不對的，因為這和數學上相違背了（數學上表示以10為底數），

計算階乘的時間復雜度：時間復雜度O(N)

// 計算階乘遞回Factorial的時間復雜度？
long long Factorial(size_t N)
{
	return N < 2 ? N : Factorial(N - 1) * N;
}

解釋：

常見的復雜度：

O(1) O(N) O(N/2) O(logN)

復雜度對比：

這個圖你是不是感覺咋好像少了一條線嘞？哈哈哈，是因為O(logN)和O(1) 基本重合了，什么原因呢？O(logN)是不是感覺怎么能和O(1)相比呢？

來，我們舉個例子：

那么這樣說的話，解決 查詢中國14億人口（已經排好序的） 中的一個人 的問題，（暴力解法需要14億次），用折半查找需要的時間則很少很少，那么最多需要多少次呢？ 31次

那么最多需要31次就可以查詢到14億人口中的一個人，

4.如何計算常見演算法的空間復雜度

空間復雜度是對一個演算法在運行程序中臨時占用存盤空間大小的量度 ，空間復雜度不是程式占用了多少bytes的空間，因為這個也沒太大意義，所以空間復雜度算的是變數的個數，空間復雜度計算規則基本跟實踐復雜度類似，也使用大O漸進表示法，

引子1：空間復雜度O(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;
	}
}

解釋：

共有變數end ， exchange ， i ( 形參：n，a[ ])，所以空間復雜度是O(1)，

你可能會問：每呼叫一次，變數不都是又用了一次嗎，不計算嗎？

其實啊，時間是累積的，空間是不累計的，回圈走了N次，重復利用的是一個空間，

引子2：空間復雜度O(N)

// 計算Fibonacci的空間復雜度？
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;
}

注釋：(long long*)malloc((n + 1)意思是開辟了（n+1）空間的long long型別的陣列，（ 見知識 動態記憶體管理 ）

解釋：

n ， fibArray ， fibArray[0] ， fibArray[1] ， i還有n+1，所以準確的空間復雜度是n+6，大O表示法則是O(N)，

引子3：空間復雜度O(N)

// 計算階乘遞回Factorial的空間復雜度？
long long Factorial(size_t N)
{
	return N < 2 ? N : Factorial(N - 1) * N;
}

解釋：

那你可能會問，函式堆疊幀創建完會在遞回回傳去的時候，再一個一個銷毀的呀！為啥是O(N)呢？

其實啊，我們也說了，要取的是最悲觀的預期，在遞回的時候，一個一個創建的空間都在同時使用，所以是O(N)，

5.有復雜度要求的演算法題練習

5.1消失的數字

我們想到的是有如下兩種思路，再次我也不再贅述，我們來研究一下第三種思路叭~~

思路3：

int missingNumber(int* nums, int numsSize)
{
    int x = 0;
    //先跟陣列中的值異或運算
    for(int i = 0; i < numsSize; i++)
    {
        x ^= nums[i];
    }

    //再跟[0,N]之間的數異或
    for(int j = 0 ; j < numsSize+1 ; j++)
    {
        x ^= j;
    }
    return x;
} 

5.2旋轉陣列

思路1：回圈K次

時間復雜度為O(N*K)

void rotate(int* nums, int numsSize, int k)
{
    //時間復雜度為O(N*K)
    while(k--)
    {
        int temp = nums[numsSize - 1];
        for(int end = numsSize - 2 ; end >= 0 ; end--)
       {
             nums[end+1] = nums[end];
       }
        nums[0] = temp;
    }
    
}

說明：時間復雜度太大，

思路2：空間換時間

時間復雜度是O(N)

思路3：（ 天才想起來的，我是廢狗！ ）

我們寫出如下代碼：

void Reverse(int* nums , int left , int right)
{
    while(left < right)
    {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
        left++;
        right--;
    }
}

void rotate(int* nums, int numsSize, int k)
{
    Reverse(nums, numsSize-k, numsSize-1);
    Reverse(nums, 0, numsSize-k-1);
    Reverse(nums, 0, numsSize-1);
}

運行結果卻失敗了，原因是因為我們的numsSize-k若是小于0怎么辦？？left是負數下標？？顯然不符合題意，所以我們需要一個判斷條件，當k大于nums的時候，回圈一圈還能回來，舉個栗子：nums = [1 , 2 , 3 ,4 , 5 ,6 , 7]，k = 10次，那么即：移動10次，而元素一共7個，也就是饒了一圈又回來了，即：移動3次，