1.數據結構前言

1.1 數據結構

數據結構(Data Structure)是計算機存儲、組織數據的?式，指相互之間存在?種或多種特定關系的數據元素的集合。沒有?種單?的數據結構對所有?途都有?，所以我們要學各式各樣的數據結構，如：線性表、樹、圖、哈希等

1.2 算法

算法(Algorithm):就是定義良好的計算過程，他取?個或?組的值為輸?，并產?出?個或?組值作為輸出。簡單來說算法就是?系列的計算步驟，?來將輸?數據轉化成輸出結果。

2.算法效率

如何衡量?個算法的好壞呢？

案例：旋轉數組https://leetcode.cn/problems/rotate-array/description/

思路：循環K次將數組所有元素向后移動?位

我們試著寫一下這道算法題，

可以將這道題拆分成：先實現一次輪轉，再循環K次，從而實現K次輪轉

將數組中最后一個數據存放到numEND中，再將剩余的數組從后往前，依次向前移動一位，

最后將numEND放到nums[0]，這樣就實現了一次輪轉，再循環K次，就成功了

void rotate(int* nums, int numsSize, int k) {while(k--){int numEND = nums[numsSize-1];for(int i=numsSize-1;i>0;i--){nums[i]=nums[i-1];}nums[0]=numEND;}}

我們試著提交，發現這段代碼并沒有提交成功，并且顯示超出時間限制

代碼點擊執行可以通過，然而點擊提交卻無法通過，那該如何衡量其好與壞呢？（這道算法的解法第6大點中給出）

2.1 復雜度的概念

算法在編寫成可執?程序后，運?時需要耗費時間資源和空間(內存)資源 。因此衡量?個算法的好壞，?般是從時間和空間兩個維度來衡量的，即時間復雜度和空間復雜度。時間復雜度主要衡量?個算法的運行快慢，?空間復雜度主要衡量?個算法運?所需要的額外空間。在計算機發展的早期，計算機的存儲容量很?。所以對空間復雜度很是在乎。但是經過計算機?業迅速發展，計算機的存儲容量已經達到了很?的程度。所以我們如今已經不需要再特別關注?個算法的空間復雜度。

2.2 復雜度的重要性

復雜度在校招中的考察已經很常?，如下：

定義：在計算機科學中，算法的時間復雜度是?個函數式T(N)，它定量描述了該算法的運?時間。時間復雜度是衡量程序的時間效率，那么為什么不去計算程序的運?時間呢？

1. 因為程序運行時間和編譯環境和運行機器的配置都有關系，比如同?個算法程序，用?個老編譯

器進行編譯和新譯器編譯，在同樣機器下運行時間不同。

2. 同?個算法程序，用?個老低配置機器和新高配置機器，運行時間也不同。
3. 并且時間只能程序寫好后測試，不能寫程序前通過理論思想計算評估。

那么算法的時間復雜度是?個函數式T(N)到底是什么呢？

這個T(N)函數式計算了程序的執行次數。

通過c語言編譯鏈接章節學習，我們知道算法程序被編譯后生成?進制指令，程序運行，就是cpu執行這些編譯好的指令。那么我們通過程序代碼或者理論思想計算出程序的執行次數的函數式T(N)，假設每句指令執行時間基本?樣(實際中有差別，但是微乎其微)，那么執行次數和運行時間就是等比正相關，這樣也脫離了具體的編譯運行環境。執行次數就可以代表程序時間效率的優劣。比如解決?個問題的算法a程序T(N) = N，算法b程序T(N) = N^2，那么算法a的效率?定優于算法b。

案例：

// 請計算?下Func1中++count語句總共執?了多少
次？
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;}
}

Func1 執?的基本操作次數：

• T (N) = N2 + 2 ? N + 10

• N = 10 T(N) = 130

• N = 100 T(N) = 10210

• N = 1000 T(N) = 1002010

通過對N取值分析，對結果影響最大的?項是 N^2

實際中我們計算時間復雜度時，計算的也不是程序的精確的執行次數，精確執行次數計算起來還是很

麻煩的(不同的?句程序代碼，編譯出的指令條數都是不?樣的)，計算出精確的執行次數意義也不大，

因為我們計算時間復雜度只是想比較算法程序的增長量級，也就是當N不斷變大時T(N)的差別，上面我

們已經看到了當N不斷變大時常數和低階項對結果的影響很小，所以我們只需要計算程序能代表增長量

級的大概執行次數，復雜度的表式通常使用大O的漸進表示法。

3.1 大O的漸進表式法

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

[!IMPORTANT]

1.時間復雜度函數式T(N)中，只保留最高階項，去掉那些低階項，因為當N不斷變大時，低階項對結果影響越來越小，當N無窮大時，就可以忽略不計了。

2. 如果最高階項存在且不是1，則去除這個項目的常數系數，因為當N不斷變大，這個系數對結果影響越來越小，當N無窮大時，就可以忽略不計了。

3. T(N)中如果沒有N相關的項目，只有常數項，用常數1取代所有加法常數。

通過以上方法，可以得到 Func1 的時間復雜度為： O(N2 )

3.2 時間復雜度計算示例

3.2.1 示例1

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

Func2執行的基本操作次數：

T (N) = 2N + 10

根據推導規則第3條得出 Func2的時間復雜度為： O(N)

3.2.2 示例2

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

Func3執行的基本操作次數：

T (N) = M + N

因此：Func2的時間復雜度為： O(N)

3.2.3 示例3

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

T (N) = 100

根據推導規則第1條得出

Func2的時間復雜度為： O(1)

3.2.4 示例4

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

strchr執行的基本操作次數：

1）若要查找的字符在字符串第?個位置，則：T (N) = 1

2）若要查找的字符在字符串最后的?個位置，則：T (N) = N

3）若要查找的字符在字符串中間位置，則：T (N) = N/2

因此：strchr的時間復雜度分為：

最好情況： O(1)

最壞情況： O(N)

平均情況： O(N)

通過上?我們會發現，有些算法的時間復雜度存在最好、平均和最壞情況。

最壞情況：任意輸?規模的最?運?次數(上界)

平均情況：任意輸?規模的期望運?次數

最好情況：任意輸?規模的最?運?次數(下界)

?O的漸進表?法在實際中?般情況關注的是算法的上界，也就是最壞運行情況。

3.2.5 示例5

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

這是冒泡排序的函數，這個函數主要是將數組中兩個相鄰的元素依次進行比較，將大的元素往后放（升序），從頭到尾將每組相鄰的元素比較完后，就能保證數組中最后那個元素是最大的（這是內層循環，當數組無限大時即循環n次），再來一趟就能把第二大的元素放到，倒數第二個位置，在進行下去循環數組長度n趟（最壞的情況），就得到了升序數組。

這樣的函數的執行次數是多少呢？舉個例子：

對于有n個元素的數組，最壞的情況代碼要執行（n-1）+(n-2)+...+2+1次，通過我們小學所學的等差數列求和公式，這段代碼一共執行了n*（n-1）/2次。我們的時間復雜度就是O($n^2$)當然這是最壞的情況，如果說數組完全有序，在比較完一趟數組之后沒有發生元素交換即exchange == 0時，代碼就只執行了（n-1）次，時間復雜度為O（n）,我們一般采取最壞的情況。

因此：BubbleSort的時間復雜度取最差情況為： O(*$N^2$ )

3.2.6 示例6

void func5(int n)
{int cnt = 1;while (cnt < n){cnt *= 2;}
}

有的時候代碼的執行次數可能是對數，就像這個函數。

分析如下：

當n接近無窮大時，底數的大小對結果影響不大。因此，?般情況下不管底數是多少都可以省略不寫，即可以表?為 log n

不同書籍的表示方式不同，以上寫法差別不大，建議使用 log n

3.2.7 示例7

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

調用?次Fac函數的時間復雜度為 O(1)而在Fac函數中，存在n次遞歸調用Fac函數

因此：階乘遞歸的時間復雜度為： O(n)

4.空間復雜度

空間復雜度也是?個數學表達式，是對?個算法在運行過程中因為算法的需要額外臨時開辟的空間。空間復雜度不是程序占用了多少bytes的空間，因為常規情況每個對象大小差異不會很大，所以空間復雜度算的是變量的個數。空間復雜度計算規則基本跟實踐復雜度類似，也使?大O漸進表示法。

注意：函數運行時所需要的棧空間(存儲參數、局部變量、?些寄存器信息等)在編譯期間已經確定好了，因此空間復雜度主要通過函數在運?時候顯式申請的額外空間來確定。

4.1 空間復雜度計算示例

4.1.1 示例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;}
}

這里我們額外創建的變量只有形參變量n和exchange

BubbleSort額外申請的空間有exchange等有限個局部變量，使用了常數個額外空間因此空間復雜度為 O(1)。

4.1.2 示例2

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

Fac遞歸調用了N次，額外開辟了N個函數棧幀，每個棧幀使用了常數個空間

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

5.常見復雜度對比

6.復雜度算法題

在了解完復雜度的概念之后，我們終于理解了在第2大點當中那道輪轉數組算法無法通過的原因，那我們如何優化我們的算法呢？

在上面的解法中，時間復雜度是O(N^2)，下面我們給出時間復雜度更低的兩種解法：

6.1思路2

空間復雜度 O(n)

申請新數組空間，先將后k個數據放到新數組中，再將剩下的數據挪到新數組中

void rotate(int* nums, int numsSize, int k) {int newArr[numsSize];k=k%numsSize;for (int i = 0; i < k; i++){newArr[i] = nums[numsSize - k + i];}for (int j = k; j < numsSize; j++){newArr[j] = nums[j - k];}for(int x=0;x<numsSize;x++){nums[x]=newArr[x];}
}

這是這種解法的第一種方式，我們創建好新數組后，將原數組nums中倒數k個元素賦值到newArr的前k個，再將nums前numsSize-k個元素賦值到newArr后numsSize-k個，最后將新數組newArr拷貝給原數組nums其中最關鍵的是k的越界問題，因為k有可能是大于numsSize的，也就是數組輪轉了超過numsSize個，甚至有可能包含了很多個numsSize，但是每循環numsSize次都是沒有意義的，都會回到原點，所以我們要在前面加上
k=k%numsSize;，也就是把k限制在numsSize內

此解法還有另一種方式，更加簡單直接

void rotate(int* nums, int numsSize, int k) {int newArr[numsSize];for(int i=0;i<numsSize;i++){newArr[(i+k)%numsSize]=nums[i];}for(int j=0;j<numsSize;j++){nums[j]=newArr[j];}
}

我們直接將原數組中nums[i]賦值給newArr[(i+k)]，我們不用分先后，直接輪轉，但是很明顯如果代碼只有這樣，可能會出現兩種問題，一是循環到后面i+k會越界,這個時候它應該回到開頭，二是i+k可能一開始就很大，超出numsSize好幾輪我們還要newArr[(i+k)%numsSize],這樣就確保(i+k)是在numsSize內的

這種解法只用了兩個或者三個并列的循環時間復雜度是O(n)，而文章最開始使用的是嵌套循環時間復雜度是O($n^2$)，這種解法我們創建了新的數組，導致我們的空間復雜度變成了O(n)，本質上是用空間換時間的方式來提高性能。

6.2思路3：

空間復雜度 O(1)

• 前n-k個逆置： 4 3 2 1 5 6 7
• 后k個逆置 ：4 3 2 1 7 6 5
• 整體逆置 ： 5 6 7 1 2 3 4

void reserve(int* arr, int begin, int end)
{while (begin < end){int tmp = arr[begin];arr[begin] = arr[end];arr[end] = tmp;begin++;end--;}}void rotate(int* nums, int numsSize, int k) {k = k % numsSize;reserve(nums, 0, numsSize - k - 1);reserve(nums, numsSize - k, numsSize - 1);reserve(nums, 0, numsSize - 1);}

我們用三次逆置的方法，從時間上在我們逆置的函數中，每次調用這個函數只會執行n/2次，我們一共調用3次，比起之前的思路時間可能更短，時間復雜度是O(n)。從空間上講，我們只是創建了兩個開始和結尾兩個變量，空間復雜度是O(1)