??前面的話??
本篇文章帶大家認識資料結構與演算法基礎，時間復雜度與空間復雜度，演算法效率分析分為兩種：第一種是時間效率，第二種是空間效率，時間效率被稱為時間復雜度，而空間效率被稱作空間復雜度， 時間復雜度主要衡量的是一個演算法的運行速度，而空間復雜度主要衡量個演算法所需要的額外空間，在計算機發展的早期，計算機的存盤容量很小，所以對空間復雜度很是在乎，但是經過計算機行業的迅速發展，計算機的存盤容量已經達到了很高的程度，所以我們如今已經不需要再特別關注一個演算法的空間復雜度，描述代碼：Java，
📒博客主頁：未見花聞的博客主頁
🎉歡迎關注🔎點贊👍收藏??留言📝
📌本文由未見花聞原創，CSDN首發！
📆首發時間：🌴2021年11月6日🌴
??堅持和努力一定能換來詩與遠方！
💭參考書籍：📚《趣學資料結構》，📚《資料結構(C語言版)》，📚《趣學演算法》
💬參考在線編程網站：🌐牛客網🌐力扣
博主的碼云gitee，平常博主寫的程式代碼都在里面，
博主的碼云github，平常博主寫的程式代碼都在里面，
🙏作者水平很有限，如果發現錯誤，一定要及時告知作者哦！感謝感謝！
📌導航小助手📌
- 🍎1.問題匯入
- 🍏1.1引入復雜度
- 🍏1.2棋盤麥子問題
- 🍎2.時間復雜度
- 🍏2.1概念
- 🍏2.2時間復雜度的計算
- 🍎3.空間復雜度
- 🍏2.1概念
- 🍏2.2空間復雜度的計算
🍎1.問題匯入
🍏1.1引入復雜度
🍊求下面序列之和∶
?
1
,
1
,
?
1
,
1
,
.
.
.
,
(
?
1
)
n
-1,1,-1,1,...,(-1)^n
?1,1,?1,1,...,(?1)n
第一種做法：
public static int sumAdd(int n) {
int sum = 0;
for (int i = 1; i <= n; i++) {
sum += (int)Math.pow(-1, i);
}
return sum;
}
該程式執行了n次，
第二種做法：
public static int sumAddPlus(int n) {
int sum = 0;
if (n % 2 == 1) {
sum = -1;
}
return sum;
}
該程式執行了1次，
可見不同的演算法，可能會有著不同的執行次數，執行的次數越少，則程式所費時間越少，說明演算法越優，
所以我們使用程式的執行次數作為判斷一個程式運行速度快慢的標準，這個執行次數就稱為一種演算法的時間復雜度，
🍏1.2棋盤麥子問題
我來帶大家認識一種恐怖的爆炸增量，相信大家都聽說過棋盤麥子的故事：
有一個古老的傳說，有一位國王的女兒不幸落水，水中有很多鱷魚，國王情急之下下令∶"誰能把公主救上來，就把女兒嫁給他，"很多人紛紛退讓，一個勇敢的小伙子挺身而出，冒著生命危險把公主救了上來，國王一看是個窮小子，想要反悔，說∶"除了女兒，你要什么都可以，"小伙子說∶"好吧，我只要一棋盤的麥子，您在第1個格子里放1粒麥子，在第2 個格子里放2粒，在第3個格子里放4粒，在第4個格子里放8粒，以此類推，每一格子里的麥子粒數都是前一格的兩倍，把這64個格子都放好了就行，我就要這么多，"國王聽后哈哈大笑，覺得小伙子的要求很容易滿足，滿口答應，結果發現，把全國的麥子都拿來，也填不完這64格……國王無奈，只好把女兒嫁給了這個小伙子，
棋盤上的64個格子究竟要放多少粒麥子?把每一個放的麥子數加起來，總和為S，則∶
S
=
1
+
2
1
+
2
2
+
2
3
+
.
.
.
+
2
63
S=1+2^1+2^2+2^3+...+2^{63}
S=1+21+22+23+...+263
等式兩邊同乘以2，得：
2
S
=
2
1
+
2
2
+
2
3
+
2
4
+
.
.
.
+
2
64
2S=2^1+2^2+2^3+2^4+...+2^{64}
2S=21+22+23+24+...+264
兩式做差，得：
S
=
2
64
?
1
=
18446744073709551615
S=2^{64}-1 = 18446744073709 551615
S=264?1=18446744073709551615
據專家統計，每個麥粒的平均重量約41.9毫克，那么這些麥粒的總重量是∶
18446744073709551615
×
41.9
=
772918576688430212668.5
（
毫
克
）
≈
7729
（
億
噸
）
18446744073709551615×41.9=772918576688430212668.5（毫克）≈7729（億噸）
18446744073709551615×41.9=772918576688430212668.5（毫克）≈7729（億噸）
全世界人口按60億計算，每人可以分得128噸!
我們稱這樣的函式為爆炸增量函式，想一想，如果演算法時間復雜度是 O ( 2 n ) O(2^n) O(2n)會怎樣?隨著n的增長，這個演算法會不會"爆掉"?經常見到有些演算法除錯沒問題，運行一段也沒問題，但關鍵的時候宕機（shutdown），例如，在線考試系統，50 個人考試沒問題，100 人考試也沒問題，如果全校1萬人考試就可能出現宕機，
注意∶宕機就是死機，指電腦不能正常作業了，包括一切原因導致的死機，計算機主機出現意外故障而死機，一些服務器（如資料庫）死鎖，服務器的某些服務停止運行都可以稱為宕機，
常見的演算法時間復雜度有以下幾類：
- 常數階，如 O ( 1 ) O(1) O(1)，
- 多項式階，如 O ( n 2 ) , O ( n 3 ) , O ( n 4 ) O(n^2),O(n^3),O(n^4) O(n2),O(n3),O(n4)等，
- 指數階，如棋盤麥子，遞回實作斐波拉契數列 O ( 2 n ) O(2^n) O(2n)，
- 對數階，如二分查找 O ( l o g 2 n ) O(log_2n) O(log2?n)，
根據對應函式的趨勢圖：
O
(
1
)
<
O
(
l
o
g
n
)
<
O
(
n
)
<
O
(
n
l
o
g
n
)
<
O
(
n
2
)
<
O
(
n
3
)
<
O
(
2
n
)
<
O
(
n
!
)
<
O
(
n
n
)
O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)
O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)
一般我們設計演算法時，時間復雜度最好小于 O ( n 2 ) O(n^2) O(n2)，
🍎2.時間復雜度
🍏2.1概念
時間復雜度的定義：在計算機科學中，演算法的時間復雜度是一個函式，它定量描述了該演算法的運行時間，一個演算法執行所耗費的時間，從理論上說，是不能算出來的，只有你把你的程式放在機器上跑起來，才能知道，但是我們需要每個演算法都上機測驗嗎？是可以都上機測驗，但是這很麻煩，所以才有了時間復雜度這個分析方式，一個演算法所花費的時間與其中陳述句的執行次數成正比例，演算法中的基本操作的執行次數，為演算法的時間復雜度，
🍏2.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--) > 0) {
count++;
}
System.out.println(count);
}
對于這個程式，首先兩層嵌套的for回圈每層都執行了n次，所以它執行的次數為n*n，即n2，然后執行單層的for回圈，執行次數為2n，最后執行了單層的while回圈，執行次數為m = 10，所以該程式一共執行的次數為
T
(
n
)
T(n)
T(n)：
T
(
n
)
=
n
2
+
2
n
+
10
T(n) = n^2 +2n + 10
T(n)=n2+2n+10
n
=
10
,
T
(
n
)
=
130
n = 10, T(n) = 130
n=10,T(n)=130
n
=
100
,
T
(
n
)
=
10210
n = 100, T(n) = 10210
n=100,T(n)=10210
n
=
1000
,
T
(
n
)
=
1002010
n = 1000, T(n) = 1002010
n=1000,T(n)=1002010
…
當
n
n
n趨近于無窮大時，我們發現除最高階外其他的低階項或常數項可以忽略，
我們實際要計算時間復雜度時，只計算它的大概的執行次數，所以對于復雜度我們取對程式執行次數起主要因素的一項，也就是最高階項，并且最高階的系數一律置為1，因為當
n
n
n趨近于無窮大時多乘一個系數少乘一個系數都對復雜度沒有很大的影響，這種方法也稱“大O的漸進表示法”，
大O符號（Big O notation）：是用于描述函式漸進行為的數學符號，
推導大O階方法：
- 用常數1取代運行時間中的所有加法常數，
- 在修改后的運行次數函式中，只保留最高階項，
- 如果最高階項存在且不是1，則去除與這個最高階項相乘的常數，得到的結果就是大O階，
另外，演算法的時間復雜度存在最好，平均，最差情況，我們所計算的時間復雜度一般為最壞情況下的復雜度，因為計算最好情況與平均情況的復雜度意義不大，最壞情況下的時間復雜度才能體現一個程式的性能好壞，
最壞情況：任意輸入規模的最大運行次數(上界)
平均情況：任意輸入規模的期望運行次數
最好情況：任意輸入規模的最小運行次數(下界)
所以該程式的時間復雜度為 O ( n 2 ) O(n^2) O(n2)
下面我們就開始來小試牛刀一下：
🍊題1
// 計算func2的時間復雜度？
void func2(int N) {
int count = 0;
for (int k = 0; k < 2 * N ; k++) {
count++;
}
int M = 10;
while ((M--) > 0) {
count++;
}
System.out.println(count);
}
該程式執行次數為
T
(
n
)
T(n)
T(n)：
T
(
n
)
=
2
n
+
10
T(n) = 2n + 10
T(n)=2n+10
時間復雜度為
O
(
n
)
O(n)
O(n)
🍊題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++;
}
System.out.println(count);
}
該程式執行次數為
T
(
n
,
m
)
T(n,m)
T(n,m)：
T
(
n
,
m
)
=
m
+
n
T(n,m) = m + n
T(n,m)=m+n
時間復雜度為
O
(
m
+
n
)
O(m + n)
O(m+n)
🍊題3
// 計算func4的時間復雜度？
void func4(int N) {
int count = 0;
for (int k = 0; k < 100; k++) {
count++;
}
System.out.println(count);
}
該程式執行次數為
T
(
n
)
T(n)
T(n)：
T
(
n
)
=
100
T(n) = 100
T(n)=100
T
(
n
)
T(n)
T(n)為一個常數，所以時間復雜度為
O
(
1
)
O(1)
O(1)
🍊題4
// 計算bubbleSort的時間復雜度？
void bubbleSort(int[] array) {
for (int end = array.length; end > 0; end--) {
boolean sorted = true;
for (int i = 1; i < end; i++) {
if (array[i - 1] > array[i]) {
Swap(array, i - 1, i);
sorted = false;
}
}
if (sorted == true) {
break;
}
}
}
該程式最壞情況下執行次數為
T
(
n
)
T(n)
T(n)：
T
(
n
)
=
n
?
1
+
n
?
2
+
.
.
.
+
1
+
0
=
n
?
(
n
?
1
)
/
2
T(n) = n - 1 + n - 2 + ... + 1 +0 =n*(n-1)/2
T(n)=n?1+n?2+...+1+0=n?(n?1)/2
時間復雜度為
O
(
n
2
)
O(n^2)
O(n2)
🍊題5
// 計算binarySearch的時間復雜度？
int binarySearch(int[] array, int value) {
int begin = 0;
int end = array.length - 1;
while (begin <= end) {
int mid = begin + ((end-begin) / 2);
if (array[mid] < value)
begin = mid + 1;
else if (array[mid] > value)
end = mid - 1;
else
return mid;
}
return -1;
}
這是一個二分查找的程式，每回圈一次，排除的元素就少一半，我們設該程式的執行次數為
T
(
n
)
T(n)
T(n)，元素個數為
n
n
n，當查找剩余元素個數為1個時，程式還需要查找一次，所以當執行
T
(
n
)
?
1
T(n)-1
T(n)?1次時，剩余的元素個數為1，則有下面等式：
n
/
2
(
T
(
n
)
?
1
)
=
1
n/2^{(T(n)-1)} = 1
n/2(T(n)?1)=1
即：
2
(
T
(
n
)
?
1
)
=
n
2^{(T(n)-1)} = n
2(T(n)?1)=n
該程式執行次數為
T
(
n
)
T(n)
T(n)：
T
(
n
)
=
l
o
g
2
n
+
1
T(n) = log_2 n + 1
T(n)=log2?n+1
時間復雜度為
O
(
l
o
g
2
n
)
或
O
(
l
o
g
n
)
O(log_2n)\ 或\ O(logn)
O(log2?n) 或 O(logn)
🍊題6
// 計算階乘遞回factorial的時間復雜度？
long factorial(int N) {
return N < 2 ? N : factorial(N-1) * N;
}
該程式需要遞回的次數為
n
n
n次，所以它的時間復雜度為
O
(
n
)
O(n)
O(n)
🍊題7
// 計算斐波那契遞回fibonacci的時間復雜度？
int fibonacci(int N) {
return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);
}
不考慮右邊最后缺失的幾次遞回，大概的遞回次數為
T
(
n
)
T(n)
T(n)
T
(
n
)
=
1
+
2
1
+
2
2
+
.
.
.
+
2
(
n
?
1
)
T(n)=1 + 2^1 + 2^2 + ...+ 2^{(n-1)}
T(n)=1+21+22+...+2(n?1)
由等比數列求和公式：
T
(
n
)
=
2
n
?
1
T(n) = 2^n - 1
T(n)=2n?1
所以斐波拉契數列遞回實作的時間復雜度為 O ( 2 n ) O(2^n) O(2n)，在前面的麥子棋盤已經可知該時間復雜度的恐怖性，
🍎3.空間復雜度
🍏2.1概念
空間復雜度是對一個演算法在運行程序中臨時占用存盤空間大小的量度 ，空間復雜度不是程式占用了多少bytes的空間，因為這個也沒太大意義，所以空間復雜度算的是變數的個數，空間復雜度計算規則基本跟時間復雜度類似，也使用大O漸進表示法，
🍏2.2空間復雜度的計算
// 計算bubbleSort的空間復雜度？
void bubbleSort(int[] array) {
for (int end = array.length; end > 0; end--) {
boolean sorted = true;
for (int i = 1; i < end; i++) {
if (array[i - 1] > array[i]) {
Swap(array, i - 1, i);
sorted = false;
}
}
if (sorted == true) {
break;
}
}
}
該程式只開辟了常數級的記憶體空間，空間復雜度為 O ( 1 ) O(1) O(1)，
// 計算fibonacci的空間復雜度？
int[] fibonacci(int n) {
long[] fibArray = new long[n + 1];
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 n+1的長整型陣列記憶體空間，空間復雜度為 O ( n ) O(n) O(n)，
// 計算階乘遞回Factorial的空間復雜度？
long factorial(int N) {
return N < 2 ? N : factorial(N-1)*N;
}
遞回求階乘一共遞回了 n n n次，每次開辟的記憶體是常數級的，使用空間復雜度為 O ( n ) O(n) O(n)，
留給讀者：遞回實作斐波拉契數列空間復雜度為多少？
答案是
O
(
2
n
)
O(2^n)
O(2n)，知道為什么嗎？思考一下吧！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/352223.html
標籤：其他