Algorithms_入门基础_时间复杂度空间复杂度
文章目錄
- 算法的基本特征 & 設計原則
- 基本特征
- 設計原則
- 評價算法的兩個重要指標
- 時間復雜度
- 定義
- 表示方法
- 如何計算時間復雜度
- 幾種常見的時間復雜度
- 如何分析時間復雜度
- 常數 O(1)
- 對數階O(logn)
- 線性階O(n)
- 線性對數階O(nlogN)
- 平方階O(n2)
- 立方階O(n3)、K次方階O(n^k)
- 時間復雜度排序
- 兩條規則
- 空間復雜度
- 概述
- O(1)
- 空間復雜度 O(n)
- 常見排序算法的復雜度
算法的基本特征 & 設計原則
基本特征
-
有窮性：一個算法必須總是（對任何合法的輸入值）在執行有窮步之后結束，且每一步都可在有窮時間內完成。
-
確定性：算法中每一條指令必須有確切的含義，讀者理解時不會產生二義性。即對于相同的輸入只能得出相同的輸出。
-
可行性：一個算法是可行的，即算法中描述的操作都是吋以逋過已經實現的基本運算執行有限次來實現的。
-
輸入：一個算法有零個或多個的輸入，這些輸入取自于某個特定的對象的集合。
-
輸出：一個算法有一個或多個的輸出，這些輸出是同輸入有著某種特定關系的量。
設計原則
通常設計一個“好”的算法應考慮達到以下目標：
-
正確性：算法應當能夠正確地解決求解問題。
-
可讀性：算法應當具有良好的可讀性，以助于人們理解。
-
健壯性：當輸入非法數據時，算法也能適當地做出反應或進行處理，而不會產生莫名其妙的輸出結果。
-
效率與低存儲量需求：效率是指算法執行的時間，存儲量需求是指算法執行過程中所需要的最大存儲空間，這兩者都與問題的規模有關。
評價算法的兩個重要指標
- 時間復雜度 ： 運行一個程序所花費的時間 O()
- 空間復雜度: 空間復雜度也不是用來計算程序實際占用的空間的。空間復雜度是對一個算法在運行過程中臨時占用存儲空間大小的一個量度，同樣反映的是一個趨勢，通常用 S(n) 來定義。
https://zhuanlan.zhihu.com/p/50479555
時間復雜度
定義
運行一個程序所花費的時間 。
舉個例子 ,如何測試我們的程序性能？ 性能測試之類的對吧-----> 主機的性能不同，數據的準確性和數據量等等 ，都會對我們的結果產生影響。
作為開發人員如何評估下呢？ --> 我們需要評估下自己的代碼，就是 時間復雜度，尋求一個最優的組合，做到心中有數。
表示方法
大O表示法 ，比如我們常見的 O(1)、O(N) 、O(nlogn)、O(n^2）、O(n+1）、O(n!)等等
如何計算時間復雜度
算法的時間復雜度，主要看算法中使用到的循環結構中代碼循環的次數（稱為“頻度”）。次數越少，算法的時間復雜度越低。
舉個例子：
a) ++x; s=0; b) for (int i=1; i<=n; i++) { ++x; s+=x; } c) for (int i=1; i<=n; i++) { for (int j=1; i<=n; j++) { ++x; s+=x; } }上邊這個例子中，a 代碼的運行了 1 次，b 代碼的運行了 n 次，c 代碼運行了 n*n 次。
所以上邊的例子而言，a 的時間復雜度為O(1)，b 的時間復雜度為O(n)，c 的時間復雜度為為O(n^2)。
如果a、b、c組成一段程序，那么算法的時間復雜度為O(n^2+n+1)。但這么表示是不對的，還需要對n^2+n+1進行簡化
簡化的過程總結為3步：
- 去掉運行時間中的所有加法常數。（例如 n^2+n+1，直接變為 n^2+n）
- 只保留最高項。（n^2+n 變成 n^2）
- 如果最高項存在但是系數不是1，去掉系數。（n^2 系數為 1）
所以，最終a、b和c合并而成的代碼的時間復雜度為O(n^2)
幾種常見的時間復雜度
可查考 維基百科 ： 時間復雜度
這里我們挑幾個常用的來 解釋一下
- 常數階：O(1)
- 對數階：O(logN)
- 線性階：O(n)
- 線性對數階：O(nlogN)
- 平方階：O(n^2)
- 立方階：O(n^3)
- K次方階：O(n^k)
- 指數階：O(2^n)
上面從上至下時間復雜度越來越大。 執行效率越來越低。
O(1)常數階 < O(logn)對數階 < O(n)線性階 < O(n^2)平方階 < O(n^3)(立方階) < O(2^n) (指數階)如何分析時間復雜度
- 最壞時間復雜度是指在最壞情況下，算法的時間復雜度。
- 平均時間復雜度是指所有可能輸入實例在等概率出現的情況下，算法的期望運行時間。
- 最好時間復雜度是指在最好情況下，算法的時間復雜度。
一般總是考慮在最壞情況下的時間復雜度，以保證算法的運行時間不會比它更長。
常數 O(1)
public class BigO {public static void main(String[] args) {int a = 1 ;// 1.運行幾次？ for (int i = 0; i < 5; i++) { // 3.運行幾次？a = a + 1 ; // 2.運行幾次？}} }來看下
public static void main(String[] args) {int a = 1 ;// 1.運行幾次？ ----> n=1次 ， T(n) = O(1)for (int i = 0; i < 5; i++) { // 3.運行幾次？ ---> n=6次 在第6次的時候跳出循環 運行了(0,1,2,3,4,5)a = a + 1 ; // 2.運行幾次？ ---> n=5次 ，T(n)是? O(5) ? O(1) ? O(n)? ---> O(1)}}上面的代碼消耗的時間并不隨著某個變量的增長而增長，運行的次數固定，那么無論這個類的代碼有多長，即使有成千上萬行，都可以用O(1)來表示它的時間復雜度。
對數階O(logn)
來看個代碼 ，算下這個的時間復雜度是 ？
// n 未知 int i = 1 ;while( i <= n){i = i * 2; }推演下：
n未知
i的值：1,2 4 8 16 32,=》2^0,2^1,2^2,2^3,.....2^n
===> 2^x=n ======>求出x就是我們運行的次數 => x=log2n =>計算機忽略掉常數 => x = logn =>O(logn)
while( i <= n){i = i * 3; //O(logn)}同樣的，上面的 雖然是乘以3 ，但是也是O(logn)， 常數忽略
需要注意的是，如果n是個常數，那么時間復雜度就是O(1)了。
經典的二分查找算法時間復雜度就是 O(logn)
假設總共有n個元素，那么每次查找的區間大小就是n，n/2，n/4，…，n/2^k，其中k是循環的次數。
在最壞情況下是在排除到只剩下最后一個值之后得到結果，即n/2^k = 1 。
即n/2^k=1，=====> 2^k=n ===? 可得k=log2n,（是以2為底，n的對數），所以時間復雜度可以表O(logn)
public static int biSearch(int[] array,int a){int lo = 0;int hi = array.length-1;int mid;while(lo <= hi) {mid = lo + (hi - lo) / 2;if(array[mid] == a) {return mid + 1;}else if(array[mid] < a) {lo = mid + 1;}else{hi = mid - 1;}}return -1;}線性階O(n)
n未知
for(i = 0 ; i < n;i++){a = a +1; }上述代碼的時間復雜度呢？
運行了多少次？ 隨著n的增長，這個運行時間是線性增長的 -----> O(n) n一定是一個未知的。
需要注意的是，如果n是個常數，那么時間復雜度就是O(1)了。
線性對數階O(nlogN)
理解了 線性對數階O(logn) ， 再來看 O(nlogN) 就很容易理解了—> 將時間復雜度為O(logn)的代碼循環N遍的話，那么它的時間復雜度就是 n * O(logN) = O(nlogN).
n未知
把 O(logn)的代碼稍微一改,外面套一層循環，就成了一個O(nlogN)了
int i = 1;for(int j = 0 ; j < n ;j++){ // 循環n次 while ( i <= n){i = i * 2; ---> O(logn)}}兩層循環， 乘法運算， n* O(logn) = O(nlogN) .
平方階O(n2)
n未知
把 O(n) 的代碼再嵌套循環一遍，它的時間復雜度就是 O(n2)
for(i = 0 ; i < n;i++){ // 乘法 n次for(int j = 0 ; j < n ;j ++){ //n次a = a +1; //運行了多少次？ O(n^2)}}如果將其中一層循環的n改成m，比如：
for(i = 0 ; i < m;i++){ // 乘法 m次for(int j = 0 ; j < n ;j ++){ //n次a = a +1; //運行了多少次？ O(m*n)}}那它的時間復雜度就變成了 O(m*n)
再來看下面的時間復雜度 ， 第二層循環 令 j = i
for(i = 0 ; i < n;i++){ // 乘法 n次for(int j = i ; j < n ;j ++){ //n次 a = a +1; //運行了多少次？ n*(n+1)/2 => O(n^2); => (n^2+n)/2 => 注意有個規律，有加減法的時候，找次數最高的那個}}分析一下
第一層的循 次數是確定的 O(n) n次，1 2 3 4 。。。n
那第二層的循環：
i=n 第二層循環運行1次
i=n-1 第二層循環運行2次
…
…
…
i=1 第二層循環運行n次
來算下第二層循環總共運行 1+2+3+……+n （等差數列求和嘛） = n*(n+1)/2 ===> 忽略所有常數=> 時間復雜度為 O(n^2)
注意有個規律，有加減法的時候，找次數最高的那個
立方階O(n3)、K次方階O(n^k)
這個類比 O(n^2)理解即可 O(n3)相當于三層n循環， O(n^k)相當于k層n循環 .
時間復雜度排序
我們優化的指標當然是時間復雜度越少也好，向O（1）靠攏 。
通常 常數階：O(1)>對數階：O(logN)> 線性階：O(n）>線性對數階：O(nlogN) 效果都是很好的。幾乎優化的空間不是很大
兩條規則
在分析一個程序的時間復雜性時，有以下兩條規則：
a) 加法規則
T(n) = T1(n) + T2(n) = O(f(n)) + O(g(n)) = O(max(f(n), g(n)))b) 乘法規則
T(n) = T1(n) * T2(n) = O(f(n)) * O(g(n)) = O( f(n) * g(n) )常見的漸近時間復雜度有：
O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)空間復雜度
概述
空間復雜度(Space Complexity)是對一個算法在運行過程中臨時占用存儲空間大小的量度。反映的是一個趨勢，通常用 S(n) 來定義
一個算法在計算機存儲器上所占用的存儲空間，包括
- 存儲算法本身所占用的存儲空間 ----Space Complexity不考慮在內
- 算法的輸入輸出數據所占用的存儲空間 ----Space Complexity不考慮在內
- 算法在運行過程中臨時占用的存儲空間 <------ 考量這個
算法的輸入輸出數據所占用的存儲空間是由要解決的問題決定的，是通過參數表由調用函數傳遞而來的，它不隨本算法的不同而改變。
存儲算法本身所占用的存儲空間與算法編寫的長短成正比，要壓縮這方面的存儲空間，就必須編寫出較短的算法。
算法在運行過程中臨時占用的存儲空間隨算法的不同而異，
- 有的算法只需要占用少量的臨時工作單元，而且不隨問題規模的大小而改變，我們稱這種算法是“就地"進行的，是節省存儲的算法；
- 有的算法需要占用的臨時工作單元數與解決問題的規模n有關，它隨著n的增大而增大，當n較大時，將占用較多的存儲單元.
空間復雜度比較常用的有：O(1)、O(n)、O(n2)
O(1)
假如算法執行所需要的臨時空間不隨著某個變量n的大小而變化，即此算法空間復雜度為一個常量，可表示為 O(1)
舉個例子
int a = 1; int b = 2 ; a++; b--;變量 a、b 所分配的空間都不隨著處理數據量變化，因此它的空間復雜度 S(n) = O(1)
空間復雜度 O(n)
變量所分配的空間都隨著處理數據量變化而變化 ，隨著變量的增大而增大。
舉個例子
j = 0 ; int[] a = new int[b]; for(i=1; i<=b; ++i) {j = i;j++; }分析一下： new了一個數組，需要開辟對應的內存空間， 數組長度為1，和數組長度為1個億，占用的臨時空間肯定是不同的。
算一下哈 1 int = 4字節 ，
我們開辟數組長度為10的int數組 ， 10 * 4Byte = 40字節
開辟1億個int ,那就是1億 * 4Byte / 1024 /1024 = 381m
可見， 一個40字節，一個381m ，空間復雜度隨著b的增長而增長
還有一點：開辟完這個數組后，后面的代碼，雖然有循環，但沒有再分配新的空間，因此，這段代碼的空間復雜度主要看int[] a = new int[b]即可，即 S(n) = O(n) 。
常見排序算法的復雜度
總結
以上是生活随笔為你收集整理的Algorithms_入门基础_时间复杂度空间复杂度的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Algorithms_入门基础_如何使用
- 下一篇： Algorithms_算法专项_Hash