- 💂 個人首頁:陶然同學
- 🤟 版權:本文由【陶然同學】原創、在CSDN首發、需要轉載請聯系部落客
- 💬 如果文章對你有幫助、歡迎關注、點贊、收藏(一鍵三連)和訂閱專欄哦
- 💅想尋找共同成長的小夥伴，請點選【Java全棧開發社群】
前言
前面我們已經介紹了，研究算法的最終目的就是如何花更少的時間，如何占用更少的記憶體去完成相
同的需求，并且
也通過案例示範了不同算法之間時間耗費和空間耗費上的差異，但我們并不能将時間占用和空間占
用量化，是以，
接下來我們要學習有關算法時間耗費和算法空間耗費的描述和分析。有關算法時間耗費分析，我們
稱之為算法的時
間複雜度分析，有關算法的空間耗費分析，我們稱之為算法的空間複雜度分析。
1.算法的時間複雜度分析
我們要計算算法時間耗費情況，首先我們得度量算法的執行時間，那麼如何度量呢？
事後分析估算方法：
比較容易想到的方法就是我們把算法執行若幹次，然後拿個計時器在旁邊計時，這種事後統計的方
法看上去的确不
錯，并且也并非要我們真的拿個電腦在旁邊計算，因為計算機都提供了計時的功能。這種統計方
法主要是通過設
計好的測試程式和測試資料，利用計算機計時器對不同的算法編制的程式的運作時間進行比較，從
而确定算法效率
的高低，但是這種方法有很大的缺陷：必須依據算法實作編制好的測試程式，通常要花費大量時間
和精力，測試完
了如果發現測試的是非常糟糕的算法，那麼之前所做的事情就全部白費了，并且不同的測試環境
(
硬體環境
)
的差别
導緻測試的結果差異也很大。
public static void main(String[] args) {
long start = System.currentTimeMillis();
int sum = 0; int n=100;
for (int i = 1; i <= n; i++) {
sum += i;
}
System.out.println("sum=" + sum);
long end = System.currentTimeMillis();
System.out.println(end-start);
} 事前分析估算方法：
在計算機程式編寫前，依據統計方法對算法進行估算，經過總結，我們發現一個進階語言編寫的程
序程式在計算機
上運作所消耗的時間取決于下列因素：
1.算法采用的政策和方案；
2.編譯産生的代碼品質；
3.
問題的輸入規模
(
所謂的問題輸入規模就是輸入量的多少
)
；
4.
機器執行指令的速度；
由此可見，抛開這些與計算機硬體、軟體有關的因素，一個程式的運作時間依賴于算法的好壞和問
題的輸入規模。
如果算法固定，那麼該算法的執行時間就隻和問題的輸入規模有關系了。
我麼再次以之前的求和案例為例，進行分析。
需求：
計算
1
到
100
的和。
第一種解法：
如果輸入量為n為1，則需要計算1次；
如果輸入量n為1億，則需要計算1億次；
public static void main(String[] args) {
int sum = 0;//執行1次
int n=100;//執行1次
for (int i = 1; i <= n; i++) {//執行了n+1次
sum += i; //執行了n次
}
System.out.println("sum=" + sum);
} 第二種解法：
如果輸入量為n為1，則需要計算1次；
如果輸入量n為1億，則需要計算1次；
public static void main(String[] args) {
int sum = 0;//執行1次
int n=100;//執行1次
sum = (n+1)*n/2;//執行1次
System.out.println("sum="+sum);
} 是以，當輸入規模為
n
時，第一種算法執行了
1+1+(n+1)+n=2n+3
次；第二種算法執行了
1+1+1=3
次。如果我們把
第一種算法的循環體看做是一個整體，忽略結束條件的判斷，那麼其實這兩個算法運作時間的差距
就是
n
和
1
的差距。
為什麼循環判斷在算法
1
裡執行了
n+1
次，看起來是個不小的數量，但是卻可以忽略呢？我們來看
下一個例子：
需求：
計算
100
個
1+100
個
2+100
個
3+...100
個
100
的結果
代碼：
public static void main(String[] args) {
int sum=0;
int n=100;
for (int i = 1; i <=n ; i++) {
for (int j = 1; j <=n ; j++) {
sum+=i;
}
}
System.out.println("sum="+sum);
} 上面這個例子中，如果我們要精确的研究循環的條件執行了多少次，是一件很麻煩的事情，并且，
由于真正計算和
的代碼是内循環的循環體，是以，在研究算法的效率時，我們隻考慮核心代碼的執行次數，這樣可
以簡化分析。
我們研究算法複雜度，側重的是當輸入規模不斷增大時，算法的增長量的一個抽象
(
規律
)
，而不是
精确地定位需要
執行多少次，因為如果是這樣的話，我們又得考慮回編譯期優化等問題，容易主次跌倒。
我們不關心編寫程式所用的語言是什麼，也不關心這些程式将跑在什麼樣的計算機上，我們隻關心
它所實作的算
法。這樣，不計那些循環索引的遞增和循環終止的條件、變量聲明、列印結果等操作，最終在分析
程式的運作時間
時，最重要的是把程式看做是獨立于程式設計語言的算法或一系列步驟。我們分析一個算法的運作
時間，最重要的
就是把核心操作的次數和輸入規模關聯起來。
1.1函數漸近增長
概念：
給定兩個函數
f(n)
和
g(n),
如果存在一個整數
N
，使得對于所有的
n>N,f(n)
總是比
g(n)
大，那麼我們說
f(n)
的增長漸近
快于
g(n)
。
概念似乎有點艱澀難懂，那接下來我們做幾個測試。
測試一：
假設四個算法的輸入規模都是
n
：
1.
算法
A1
要做
2n+3
次操作，可以這麼了解：先執行
n
次循環，執行完畢後，再有一個
n
次循環，最後有
3
次運算；
2.算法A2
要做
2n
次操作；
3.
算法
B1
要做
3n+1
次操作，可以這個了解：先執行
n
次循環，再執行一個
n
次循環，再執行一個
n
次
循環，最後有
1 次運算。
4.算法B2
要做
3n
次操作；
那麼，上述算法，哪一個更快一些呢？
通過資料表格，比較算法
A1
和算法
B1
：
當輸入規模
n=1
時，
A1
需要執行
5
次，
B1
需要執行
4
次，是以
A1
的效率比
B1
的效率低；
當輸入規模
n=2
時，
A1
需要執行
7
次，
B1
需要執行
7
次，是以
A1
的效率和
B1
的效率一樣；
當輸入規模
n>2
時，
A1
需要的執行次數一直比
B1
需要執行的次數少，是以
A1
的效率比
B1
的效率高；
是以我們可以得出結論：
當輸入規模
n>2
時，算法
A1
的漸近增長小于算法
B1
的漸近增長
通過觀察折線圖，我們發現，随着輸入規模的增大，算法
A1
和算法
A2
逐漸重疊到一塊，算法
B1
和
算法
B2
逐漸重疊
到一塊，是以我們得出結論：
随着輸入規模的增大，算法的常數操作可以忽略不計
測試二：
假設四個算法的輸入規模都是
n
：
1.
算法
C1
需要做
4n+8
次操作
2.
算法
C2
需要做
n
次操作
3.
算法
D1
需要做
2n^2
次操作
4.算法D2
需要做
n^2
次操作
那麼上述算法，哪個更快一些？
通過資料表格，對比算法
C1
和算法
D1
：
當輸入規模
n<=3
時，算法
C1
執行次數多于算法
D1
，是以算法
C1
效率低一些；
當輸入規模
n>3
時，算法
C1
執行次數少于算法
D1
，是以，算法
D2
效率低一些，
是以，總體上，算法
C1
要優于算法
D1.
通過折線圖，對比對比算法
C1
和
C2
：
随着輸入規模的增大，算法
C1
和算法
C2
幾乎重疊
通過折線圖，對比算法
C
系列和算法
D
系列：
随着輸入規模的增大，即使去除
n^2
前面的常數因子，
D
系列的次數要遠遠高于
C
系列。
是以，可以得出結論：
随着輸入規模的增大，與最高次項相乘的常數可以忽略
測試三：
假設四個算法的輸入規模都是
n
：
算法
E1:
2n^2+3n+1;
算法
E2
：
n^2
算法
F1
：
2n^3+3n+1
算法
F2
：
n^3
那麼上述算法，哪個更快一些？
通過資料表格，對比算法
E1
和算法
F1
：
當
n=1
時，算法
E1
和算法
F1
的執行次數一樣；
當
n>1
時，算法
E1
的執行次數遠遠小于算法
F1
的執行次數；
是以算法
E1
總體上是由于算法
F1
的。
通過折線圖我們會看到，算法
F
系列随着
n
的增長會變得特塊，算法
E
系列随着
n
的增長相比較算法
F
來說，變得比較
慢，是以可以得出結論：
最高次項的指數大的，随着
n
的增長，結果也會變得增長特别快
測試四：
假設五個算法的輸入規模都是
n
：
算法
G
：
n^3;
算法
H:
n^2;
算法
I
：
n:
算法
J
：
logn
算法
K:
那麼上述算法，哪個效率更高呢？
通過觀察資料表格和折線圖，很容易可以得出結論：
算法函數中
n
最高次幂越小，算法效率越高
總上所述，在我們比較算法随着輸入規模的增長量時，可以有以下規則：
1.
算法函數中的常數可以忽略；
2.
算法函數中最高次幂的常數因子可以忽略；
3.
算法函數中最高次幂越小，算法效率越高。
1.2算法時間複雜度
1.2.1大O記法
定義：
在進行算法分析時，語句總的執行次數
T(n)
是關于問題規模
n
的函數，進而分析
T(n)
随着
n
的變化情
況并确定
T(n)
的
量級。算法的時間複雜度，就是算法的時間量度，記作
:T(n)=O(f(n))
。它表示随着問題規模
n
的增
大，算法執行時間
的增長率和
f(n)
的增長率相同，稱作算法的漸近時間複雜度，簡稱時間複雜度，其中
f(n)
是問題規模
n
的某個函數。
在這裡，我們需要明确一個事情：
執行次數
=
執行時間
用大寫
O()
來展現算法時間複雜度的記法，我們稱之為大
O
記法。一般情況下，随着輸入規模
n
的增
大，
T(n)
增長最
慢的算法為最優算法。
下面我們使用大
O
表示法來表示一些求和算法的時間複雜度：
算法一：
public static void main(String[] args) {
int sum = 0;//執行1次
int n=100;//執行1次
sum = (n+1)*n/2;//執行1次
System.out.println("sum="+sum);
} 算法二：
public static void main(String[] args) {
int sum = 0;//執行1次
int n=100;//執行1次
for (int i = 1; i <= n; i++) {
sum += i;//執行了n次
}
System.out.println("sum=" + sum);
} 算法三：
public static void main(String[] args) {
int sum=0;//執行1次
int n=100;//執行1次
for (int i = 1; i <=n ; i++) {
for (int j = 1; j <=n ; j++) {
sum+=i;//執行n^2次
}
}
System.out.println("sum="+sum);
} 如果忽略判斷條件的執行次數和輸出語句的執行次數，那麼當輸入規模為
n
時，以上算法執行的次
數分别為：
算法一：
3
次
算法二：
n+3
次
算法三：
n^2+2
次
如果用大
O
記法表示上述每個算法的時間複雜度，應該如何表示呢？基于我們對函數漸近增長的分
析，推導大
O
階
的表示法有以下幾個規則可以使用：
1.
用常數
1
取代運作時間中的所有加法常數；
2.
在修改後的運作次數中，隻保留高階項；
3.
如果最高階項存在，且常數因子不為
1
，則去除與這個項相乘的常數；
是以，上述算法的大
O
記法分别為：
算法一：
O(1)
算法二：
O(n)
算法三：
O(n^2)
1.2.2常見的大O階
1.
線性階
一般含有非嵌套循環涉及線性階，線性階就是随着輸入規模的擴大，對應計算次數呈直線增長，例
如：
public static void main(String[] args) {
int sum = 0;
int n=100;
for (int i = 1; i <= n; i++) {
sum += i;
}
System.out.println("sum=" + sum);
} 上面這段代碼，它的循環的時間複雜度為
O(n),
因為循環體中的代碼需要執行
n
次
2.
平方階
一般嵌套循環屬于這種時間複雜度
public static void main(String[] args) {
int sum=0,n=100;
for (int i = 1; i <=n ; i++) {
for (int j = 1; j <=n ; j++) {
sum+=i; }
}
System.out.println(sum);
} 上面這段代碼，
n=100
，也就是說，外層循環每執行一次，内層循環就執行
100
次，那總共程式想
要從這兩個循環
中出來，就需要執行
100*100
次，也就是
n
的平方次，是以這段代碼的時間複雜度是
O(n^2).
3.
立方階
一般三層嵌套循環屬于這種時間複雜度
public static void main(String[] args) {
int x=0,n=100;
for (int i = 1; i <=n ; i++) {
for (int j = i; j <=n ; j++) {
for (int j = i; j <=n ; j++) {
x++;
}
}
}
System.out.println(x);
} 上面這段代碼，
n=100
，也就是說，外層循環每執行一次，中間循環循環就執行
100
次，中間循環
每執行一次，最
内層循環需要執行
100
次，那總共程式想要從這三個循環中出來，就需要執行
100
100
100
次，也就
是
n
的立方，所
以這段代碼的時間複雜度是
O(n^3).
4.
對數階
對數，屬于高中數學的内容，我們分析程式以程式為主，數學為輔，是以不用過分擔心。
int i=1,n=100;
while(i<n){
i = i*2;
} 由于每次
i*2
之後，就距離
n
更近一步，假設有
x
個
2
相乘後大于
n
，則會退出循環。由于是
2^x=n,
得
到
x=log(2)n,
所
以這個循環的時間複雜度為
O(logn);
對于對數階，由于随着輸入規模
n
的增大，不管底數為多少，他們的增長趨勢是一樣的，是以我們
會忽略底數。
5.
常數階
一般不涉及循環操作的都是常數階，因為它不會随着
n
的增長而增加操作次數。例如：
public static void main(String[] args) {
int n=100;
int i=n+2;
System.out.println(i);
} 上述代碼，不管輸入規模
n
是多少，都執行
2
次，根據大
O
推導法則，常數用
1
來替換，是以上述代
碼的時間複雜度 為O(1)
下面是對常見時間複雜度的一個總結：
1.2.3函數調用的時間複雜度分析
之前，我們分析的都是單個函數内，算法代碼的時間複雜度，接下來我們分析函數調用過程中時間
複雜度。
案例一：
public static void main(String[] args) {
int n=100;
for (int i = 0; i < n; i++) {
show(i);
}
}private static void show(int i) {
System.out.println(i);
}
} 在
main
方法中，有一個
for
循環，循環體調用了
show
方法，由于
show
方法内部隻執行了一行代碼，
是以
show
方法
的時間複雜度為
O(1),
那
main
方法的時間複雜度就是
O(n)
案例二：
public static void main(String[] args) {
int n=100;
for (int i = 0; i < n; i++) {
show(i);
}
}
private static void show(int i) {
for (int j = 0; j < i; i++) {
System.out.println(i);
}
} 在
main
方法中，有一個
for
循環，循環體調用了
show
方法，由于
show
方法内部也有一個
for
循環，
是以
show
方法
的時間複雜度為
O(n),
那
main
方法的時間複雜度為
O(n^2)
案例三：
public static void main(String[] args) {
int n=100;
show(n);
for (int i = 0; i < n; i++) {
show(i);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.println(j);
}
}
}
private static void show(int i) {
for (int j = 0; j < i; i++) {
System.out.println(i);
}
} 在
show
方法中，有一個
for
循環，是以
show
方法的時間複雜度為
O(n),
在
main
方法中，
show(n)
這行
代碼内部執行
的次數為
n
，第一個
for
循環内調用了
show
方法，是以其執行次數為
n^2,
第二個嵌套
for
循環内隻執行
了一行代碼，
是以其執行次數為
n^2,
那麼
main
方法總執行次數為
n+n^2+n^2=2n^2+n
。根據大
O
推導規則，去掉
n
保留最高階
項，并去掉最高階項的常數因子
2
，是以最終
main
方法的時間複雜度為
O(n^2)
1.2.4最壞情況
從心理學角度講，每個人對發生的事情都會有一個預期，比如看到半杯水，有人會說：哇哦，還有
半杯水哦！但也
有人會說：天哪，隻有半杯水了。一般人處于一種對未來失敗的擔憂，而在預期的時候趨向做最壞
的打算，這樣即
使最糟糕的結果出現，當事人也有了心理準備，比較容易接受結果。假如最糟糕的結果并沒有出
現，當事人會很快 樂。
算法分析也是類似，假如有一個需求：
有一個存儲了
n
個随機數字的數組，請從中查找出指定的數字。
public int search(int num){
int[] arr={11,10,8,9,7,22,23,0};
for (int i = 0; i < arr.length; i++) {
if (num==arr[i]){
return i;
}
}
return -1;
} 最好情況：
查找的第一個數字就是期望的數字，那麼算法的時間複雜度為
O(1)
最壞情況：
查找的最後一個數字，才是期望的數字，那麼算法的時間複雜度為
O(n)
平均情況：
任何數字查找的平均成本是
O(n/2)
最壞情況是一種保證，在應用中，這是一種最基本的保障，即使在最壞情況下，也能夠正常提供服
務，是以，除非
特别指定，我們提到的運作時間都指的是最壞情況下的運作時間。
2.算法的空間複雜度分析
計算機的軟硬體都經曆了一個比較漫長的演變史，作為為運算提供環境的記憶體，更是如此，從早些
時候的
512k,
經
曆了
1M
，
2M
，
4M...
等，發展到現在的
8G
，甚至
16G
和
32G
，是以早期，算法在運作過程中對記憶體
的占用情況也是 一個經常需要考慮的問題。我麼可以用算法的空間複雜度來描述算法對記憶體的占用。
2.1java中常見記憶體占用
1.
基本資料類型記憶體占用情況：
2.計算機通路記憶體的方式都是一次一個位元組
3.
一個引用（機器位址）需要
8
個位元組表示：
例如：
Date date = new Date(),
則
date
這個變量需要占用
8
個位元組來表示
4.
建立一個對象，比如
new Date()
，除了
Date
對象内部存儲的資料
(
例如年月日等資訊
)
占用的内
存，該對象本身也
有記憶體開銷，每個對象的自身開銷是
16
個位元組，用來儲存對象的頭資訊。
5.
一般記憶體的使用，如果不夠
8
個位元組，都會被自動填充為
8
位元組：
6.java
中數組被被限定為對象，他們一般都會因為記錄長度而需要額外的記憶體，一個原始資料類型
的數組一般需要
24
位元組的頭資訊
(16
個自己的對象開銷，
4
位元組用于儲存長度以及
4
個填充位元組
)
再加上儲存值所需的
記憶體。
2.2算法的空間複雜度
了解了
java
的記憶體最基本的機制，就能夠有效幫助我們估計大量程式的記憶體使用情況。
算法的空間複雜度計算公式記作：
S(n)=O(f(n)),
其中
n
為輸入規模，
f(n)
為語句關于
n
所占存儲空間
的函數。
案例：
對指定的數組元素進行反轉，并傳回反轉的内容。
解法一：
public static int[] reverse1(int[] arr){
int n=arr.length;//申請4個位元組
int temp;//申請4個位元組
for(int start=0,end=n-1;start<=end;start++,end--){
temp=arr[start];
arr[start]=arr[end];
arr[end]=temp;
}
return arr;
} 解法二：
public static int[] reverse2(int[] arr){
int n=arr.length;//申請4個位元組
int[] temp=new int[n];//申請n*4個位元組+數組自身頭資訊開銷24個位元組
for (int i = n-1; i >=0; i--) {
temp[n-1-i]=arr[i];
}
return temp;
} 忽略判斷條件占用的記憶體，我們得出的記憶體占用情況如下：
算法一：
不管傳入的數組大小為多少，始終額外申請
4+4=8
個位元組；
算法二：
4+4n+24=4n+28;
根據大
O
推導法則，算法一的空間複雜度為
O(1),
算法二的空間複雜度為
O(n),
是以從空間占用的角
度講，算法一要
優于算法二。
由于
java
中有記憶體垃圾回收機制，并且
jvm
對程式的記憶體占用也有優化（例如即時編譯），我們無
法精确的評估一
個
java
程式的記憶體占用情況，但是了解了
java
的基本記憶體占用，使我們可以對
java
程式的記憶體占用
情況進行估算。
由于現在的計算機裝置記憶體一般都比較大，基本上個人計算機都是
4G
起步，大的可以達到
32G
，
是以記憶體占用一般
情況下并不是我們算法的瓶頸，普通情況下直接說複雜度，預設為算法的時間複雜度。
但是，如果你做的程式是嵌入式開發，尤其是一些傳感器裝置上的内置程式，由于這些裝置的記憶體
很小，一般為幾
kb
，這個時候對算法的空間複雜度就有要求了，但是一般做
java
開發的，基本上都是伺服器開發，
一般不存在這樣 的問題。