算法複雜度：如何計算算法的執行效率和資源消耗

一、算法複雜度

算法本質是“快”和“省”。從時間上考慮是時間複雜度（快不快），從空間上考慮是空間複雜度（占用記憶體多不多）。

算法複雜度記作O(n)，表示資料規模為n的情況下，算法使用的時間和空間資源，也就是代碼執行花費的時間和空間随着n增大變化的趨勢。

二、時間複雜度

1、計算方法：

沒有循環，時間複雜度：O(1)

 有循環：從最内層循環開始,

  1、确定變量取值範圍

  2、确定變量每次取值的時間複雜度，記為f(n)

  3、循環相加f(n)

 重複1到3步，即可計算出嵌套循環的時間複雜度

2、簡單計算方法：

（1）計算循環執行次數最多的代碼

（2）總複雜度=量級最大的複雜度

時間複雜度比較：

O(1) < O(logn) < O(n) < O(nlogn)<O(n^2)

（1）、O(1)

public void method1(int n){

        int a = 5; // 執行1次

        int b = 6; // 執行1次

        int c = a + b;// 執行1次

        System.out.println(c);// 執行1次

}           

沒有循環，時間複雜度：O(1)

（2）、O(logn)

public void method10(int n){

        for (int i = 1 ; i <= n; i*=2) {

        System.out.println("heihei");

        }

}           

i取值範圍：2的0次方，2的1次方，2的2次方...2的log2的n次方。

執行次數為:1+log2的n

忽略系數，時間複雜度為：O(logn)

（3）、 O(n)

public void method2(int n){

        for (int i = 1 ; i <= n; ++i) {

        System.out.println("haha"); // 第3行

        }

}           

i取值：1,2,3,4...,n

執行次數：n

時間複雜度為：O(n)

（4）、O(nlogn)

public void method8(int n){

        for(int i=1;i<=n;i*=2){

        System.out.println("haha");

        for(int j=1;j<=n;++j){

        System.out.println("heihei");

        }

        }

}           

第二個for執行次數為：n

第一個for實際取值範圍：

i = 2的0次方 時，第二個for執行n次

i = 2的1次方 時，第二個for執行n次

i = 2的2次方 時，第二個for執行n次

...

i = 2的log2的n時，執行n次

執行次數：n + n + n + ....+n （一共log2的n + 1 個 n）= n * (1 + log2的n)

忽略系數，時間複雜度：O(nlogn)

（5）、O(n^2)

public void method3(int n){

        for (int i = 1 ; i <= n; ++i) { // 第2行 第1層嵌套

        System.out.println("haha"); // 第3行

        for (int j = 1 ; j <= n; ++j) { // 第4行 第2層嵌套

        System.out.println("heihei");// 第5行

        }

        }

}           

第二個for執行次數：n

第一個for實際取值：

i = 1, 第二個for 執行 n 次

i = 2, 第二個for 執行 n 次

...

i = n, 第二個for執行 n 次

總共執行次數：n+n+...+n （一共 n 個 n）= n * n

時間複雜度：O(n^2)

3、最好，最壞，平均，均攤時間複雜度

最好時間複雜度：在最理想的情況下，執行這段代碼的時間複雜度。就是代碼最少執行多少次。

最壞時間複雜度：在最糟糕的情況下，執行這段代碼的時間複雜度。就是代碼最多------------------------------------執行多少次。

平均複雜度：最好與最壞的情況下一定會存在這其他的情況，累加 這些情況下的時間複雜度 乘以 每種情況出現的頻率 即可求出平均時間複雜度。

平均時間複雜度 = 從i=1 到 i = n 的 O(i)*P(i) 總和。

O(i):i情況下花費的時間

P(i):出現i這種情況的機率

三、空間複雜度

空間複雜度全稱：漸進空間複雜度。

表示算法的存儲空間與資料規模之間的增長關系。比如将一個數組拷貝到另一個數組中，就是相當于空間擴大了一倍，比如跳躍表，hashmap的擴容。

由于現在硬體相對比較便宜，是以在開發中常常會利用空間來換時間，比如緩存技術，還有資料結構中的跳躍表。

在實際開發中我們也更關注代碼的時間複雜度，而用于執行效率的提升

關注私信可擷取更多課程資料