這篇文章是時間復(fù)雜度分析的第二篇。在前一篇文章中，我們從0推導(dǎo)出了為什么要用時間復(fù)雜度，時間復(fù)雜度如何分析以及時間復(fù)雜度的表示三部分內(nèi)容。這篇文章，是對一些常用的時間復(fù)雜度進行一個總結(jié)，相當(dāng)于是一個小結(jié)論

1.常見的大O階

1.1線性階

一般含有非嵌套循環(huán)（就是單層循環(huán)）涉及線性階，線性階就是隨著輸入規(guī)模的擴大，對應(yīng)計算次數(shù)呈直線增長，例如下面的代碼：

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);}

上面這段代碼，它的循環(huán)的時間復(fù)雜度為O(n)，因為循環(huán)體中的代碼需要執(zhí)行n次

1.2平方階

一般嵌套循環(huán)（就是雙層循環(huán)）屬于這種時間復(fù)雜度

    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);}

上面這段代碼，n=100，也就是說，外層循環(huán)每執(zhí)行一次，內(nèi)層循環(huán)就執(zhí)行100次，那總共程序想要從這兩個循環(huán)中出來，就需要執(zhí)行100*100次，也就是n的平方次，所以這段代碼的時間復(fù)雜度是O(n^2)

1.3立方階

一般三層嵌套循環(huán)屬于這種時間復(fù)雜度

public static void main(String[] args) {int x = 0;int n = 100;for (int i = 1; i <=n ; i++) {for (int j = 1; j <=n ; j++) {for (int k = 1; k <=n ; k++) {x ++; }}}System.out.println("x="+x);}

上面這段代碼，n=100，也就是說，外層循環(huán)每執(zhí)行一次，中間循環(huán)循環(huán)就執(zhí)行100次，中間循環(huán)每執(zhí)行一次，最內(nèi)層循環(huán)需要執(zhí)行100次，那總共程序想要從這三個循環(huán)中出來，就需要執(zhí)行100*100*100次，也就是n的立方，所以這段代碼的時間復(fù)雜度是O(n^3)

1.4對數(shù)階

對數(shù)，屬于高中數(shù)學(xué)的內(nèi)容，我們分析程序以程序為主，數(shù)學(xué)為輔，所以不用過分擔(dān)心。

    public static void main(String[] args) {int i = 0;int n = 100;while (i<n){i = i*2;}System.out.println("i="+i);}

分析：

由于每次i*2之后，就距離n更近一步。我們假設(shè)有x個2相乘后大于n，那么x個2相乘后就會退出循環(huán)。那么就有公式：2^x=n，得到x=log(2)n。所以這個循環(huán)的時間復(fù)雜度為O(logn)；

問：為什么底數(shù)可以忽略？
答：對于對數(shù)階，由于隨著輸入規(guī)模n的增大，不管底數(shù)為多少，他們的增長趨勢是一樣的，所以我們會忽略底數(shù)。（其實就是找輸入規(guī)模n與執(zhí)行次數(shù)之間的抽象關(guān)系，抓取主要的，忽略次要的）

下面給出表和圖，可以體會一下增長趨勢：

?

1.5常數(shù)階

一般不涉及循環(huán)操作的都是常數(shù)階，因為它不會隨著n的增長而增加操作次數(shù)。例如︰

 public static void main(String[] args) {int n = 100;int i = n+2;System.out.println("i="+i);}

上述代碼，不管輸入規(guī)模n是多少，都執(zhí)行2次，根據(jù)大O推導(dǎo)法則，常數(shù)用1來替換，所以上述代碼的時間復(fù)雜度為O(1)

1.6小結(jié)

下面是對常見時間復(fù)雜度的一個總結(jié)：

他們的時間復(fù)雜度從高到低依次是：

????????????????O(1)<O( log(n) )<O(n)<O(n*log(n))<O(n^2)<O(n^3)?

根據(jù)前面的折線圖分析，我們會發(fā)現(xiàn)，從平方階開始，隨著輸入規(guī)模的增大，時間成本會急劇增大，所以，我們的算法，盡可能的追求的是O(1)，O(log(n))，O(n),O(n^log(n))這幾種時間復(fù)雜度，而如果發(fā)現(xiàn)算法的時間復(fù)雜度為平方階、立方階或者更復(fù)雜的，那我們可以分為這種算法是不可取的，需要優(yōu)化。

2.函數(shù)調(diào)用的時間復(fù)雜度分析

之前，我們分析的都是單個函數(shù)內(nèi)，算法代碼的時間復(fù)雜度，接下來我們分析函數(shù)調(diào)用過程中時間復(fù)雜度。

2.1幾個案例

?案例一：

public static void main(String[] args) {int n = 100;for (int i = 0; i < n; i++) {show(i);}}public static void show(int i){System.out.println(i);}

在main方法中，有一個for循環(huán)，循環(huán)體調(diào)用了show方法，由于show方法內(nèi)部只執(zhí)行了一行代碼，所以show的時間復(fù)雜度為O(1)，那main方法的時間復(fù)雜度就是O(n)

案例二：

public static void main(String[] args) {int n = 100;for (int i = 0; i < n; i++) {show(i);}}public static void show(int i){for (int j = 0; j < i; j++) {System.out.println(i);}}

在main方法中，有一個for循環(huán)，循環(huán)體調(diào)用了show方法，由于show方法內(nèi)部也有一個for循環(huán)，所以show方法的時間復(fù)雜度為O(n)，那main方法的時間復(fù)雜度為O(n^2)

案例三：

public static void main(String[] args) {int n = 100;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);}}}public static void show(int i){for (int j = 0; j < i; j++) {System.out.println(i);}}

在show方法中，有一個for循環(huán)，所以show方法的時間復(fù)雜度為o(n)，在main方法中，show(n)這行代碼內(nèi)部執(zhí)行的次數(shù)為n，第一個for循環(huán)內(nèi)調(diào)用了show方法，所以其執(zhí)行次數(shù)為n^2，第二個嵌套for循環(huán)內(nèi)只執(zhí)行了一行代碼，所以其執(zhí)行次數(shù)為n^2,那么main方法總執(zhí)行次數(shù)為n+n^2+n^2=2n^2+n。

根據(jù)大O推導(dǎo)規(guī)則，去掉n保留最高階項，并去掉最高階項的常數(shù)因子2，所以最終main方法的時間復(fù)雜度為O(n^2)

2.2最壞情況

從心理學(xué)角度講，每個人對發(fā)生的事情都會有一個預(yù)期，比如看到半杯水，有人會說︰哇哦，還有半杯水哦！但也有人會說∶天哪，只有半杯水了。一般人處于一種對未來失敗的擔(dān)憂，而在預(yù)期的時候趨向做最壞的打算，這樣即使最糟糕的結(jié)果出現(xiàn)，當(dāng)事人也有了心理準(zhǔn)備，比較容易接受結(jié)果。假如最糟糕的結(jié)果并沒有出現(xiàn)，當(dāng)事人會很快樂。
算法分析也是類似，假如有一個需求∶
????????????????有一個存儲了n個隨機數(shù)字的數(shù)組，請從中查找出指定的數(shù)字。

public static void main(String[] args) {int a = search(5);System.out.println(a);}public static int search(int num){int[] arr = {11,5,3,6,7,15,6,9};for (int i = 0; i < arr.length; i++) {if (num == arr[i]) {return i;}}return -1;}

最好情況：
????????查找的第一個數(shù)字就是期望的數(shù)字，那么算法的時間復(fù)雜度為O(1)

最壞情況：
????????查找的最后一個數(shù)字，才是期望的數(shù)字，那么算法的時間復(fù)雜度為O(n)

平均情況：
????????任何數(shù)字查找的平均成本是O(n/2)

最壞情況是一種保證，在應(yīng)用中，這是一種最基本的保障，即使在最壞情況下，也能夠正常提供服務(wù)，所以，除非特別指定，我們提到的運行時間都指的是最壞情況下的運行時間。

3.小結(jié)

這篇文章，我們總結(jié)了一些常見的大O階，然后給出了相應(yīng)的表格，這屬于是一種結(jié)論，可以記下來的。然后我們分析了函數(shù)調(diào)用時的時間復(fù)雜度，其實和之前的分析方法是一樣的。最后，我們講了一下最壞情況的分析。

至此，算法的時間復(fù)雜度的講解已經(jīng)完畢了。如果有失誤的地方，敬請各位指出，謝謝大家！

?