目錄
1.時間復雜度
2.時間復雜度計算例題
3.空間復雜度
1.時間復雜度
算法中的基本操作的執行次數，為算法的時間復雜度。
如何表達 時間復雜度？
大O的漸進表示法
實際中我們計算時間復雜度時，我們其實并不一定要計算精確的執行次數，而只需要 大概執行次數，那么這里我們 使用大 O 的漸進表示法。
1、用常數1取代運行時間中的所有加法常數。2、在修改后的運行次數函數中，只保留最高階項。3、如果最高階項存在且不是1，則去除與這個項目相乘的常數。得到的結果就是大O階
舉例：
// 請計算一下 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 );}
?題解：
Func1 執行的基本操作次數 ：F(N)=N^2+2*N+10;(1) 用常數1取代運行時間中的所有加法常數。F(N)=N^2+2*N+1；（2） 在修改后的運行次數函數中，只保留最高階項。F(N)=N^2;=>O(N^2);
通過上面我們會發現大O的漸進表示法去掉了那些對結果影響不大的項，簡潔明了的表示出了執行次數。 ?
另外有些算法的時間復雜度存在最好、平均和最壞情況：
最壞情況：任意輸入規模的最大運行次數 ( 上界 )平均情況：任意輸入規模的期望運行次數最好情況：任意輸入規模的最小運行次數 ( 下界 )
一般情況下時間復雜度是算法的最壞運行情況
O(N)中N表示問題的規模
2.時間復雜度計算例題
例題1：
// 計算 func2 的時間復雜度？void func2 ( 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 );}
答案及分析：
基本操作執行了M+N次，有兩個未知數M和N，時間復雜度為 O(N+M)?
例題2：
// 計算 func3 的時間復雜度？void func3 （ int N ) {int count = 0 ;for ( int k = 0 ; k < 100 ; k ++ ) {count ++ ;}System . out . println ( count );}
?答案及分析：
基本操作執行了100次，通過推導大O階方法，時間復雜度為 O(1)
?例題3：
// 計算 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 ;}}}
?答案及分析：
F(N)=(N-1+N-2+N-3……)==(（N-1+1）*N)/2==0.5*N^2;
通過推導大 O 階方法 + 時間復雜度一般看最壞，時間 復雜度為 O(N^2)
?例題4：
// 計算 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 ;elsereturn mid ;}return - 1 ;}
?答案及分析：
方法1：
對于不能直接看出的并較復雜的問題，可以采用數學歸納法
?答案：
?方法2：
N/(2^x)?=1（x為循環的執行次數）
x的解：
例題 5
// 計算階乘遞歸 factorial 的時間復雜度？long factorial ( int N ) {return N < 2 ? N : factorial ( N - 1 ) * N ;}
對于不能直接看出的并較復雜的問題，可以采用數學歸納法，但對于遞歸我們有專門總結的方法。
F（N）=遞歸的次數*每次遞歸代碼的執行次數
?答案及分析：
通過計算分析發現基本操作遞歸了 N次， 每次遞歸代碼的執行次數為1 時間復雜度為O(N)
例題6：
// 計算斐波那契遞歸 fifibonacci 的時間復雜度？int fifibonacci ( int N ) {return N < 2 ? N : fifibonacci ( N - 1 ) + fifibonacci ( N - 2 );}
??答案及分析：
對于不能直接看出的并較復雜的問題，可以采用數學歸納法（不展開）
面對這種多遞歸入口的題，可以使用補全法。
何為補全法？
以F4為例
F（N）：?
?
1+2+4+……+2^(N-1)
=2^N-1;
O(2^N)
3.空間復雜度
空間復雜度是對一個算法在運行過程中 臨時占用存儲空間大小的量度 。空間復雜度不是程序占用了多少 bytes 的空 間，因為這個也沒太大意義，所以空間復雜度算的是變量的個數
空間復雜度計算規則基本跟時間復雜度類似 ，也 使用大 O 漸進表示法 。
無論什么類型，只看開了多少的空間
?例題1：
// 計算 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)
例題2：
// 計算 fifibonacci 的空間復雜度？int [] fifibonacci ( int n ) {long [] fifibArray = new long [ n + 1 ];fifibArray [ 0 ] = 0 ;fifibArray [ 1 ] = 1 ;for ( int i = 2 ; i <= n ; i ++ ) {fifibArray [ i ] = fifibArray [ i - 1 ] + fifibArray [ i - 2 ];}return fifibArray ;}
?答案及分析：
動態開辟了N個空間，空間復雜度為 O(N)
例題3：
// 計算階乘遞歸 Factorial 的空間復雜度？long factorial ( int N ) {return N < 2 ? N : factorial ( N - 1 ) * N ;}
??答案及分析：
遞歸調用了 N 次，開辟了 N 個棧幀，每個棧幀使用了常數個空間。空間復雜度為 O(N)
以上為我個人的小分享，如有問題，歡迎討論！！！?
都看到這了，不如關注一下，給個免費的贊?
