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

1.常見的大O階

1.1線性階

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

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)的時(shí)間復(fù)雜度為O(n)，因?yàn)檠h(huán)體中的代碼需要執(zhí)行n次

1.2平方階

一般嵌套循環(huán)（就是雙層循環(huán)）屬于這種時(shí)間復(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，也就是說(shuō)，外層循環(huán)每執(zhí)行一次，內(nèi)層循環(huán)就執(zhí)行100次，那總共程序想要從這兩個(gè)循環(huán)中出來(lái)，就需要執(zhí)行100*100次，也就是n的平方次，所以這段代碼的時(shí)間復(fù)雜度是O(n^2)

1.3立方階

一般三層嵌套循環(huán)屬于這種時(shí)間復(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，也就是說(shuō)，外層循環(huán)每執(zhí)行一次，中間循環(huán)循環(huán)就執(zhí)行100次，中間循環(huán)每執(zhí)行一次，最內(nèi)層循環(huán)需要執(zhí)行100次，那總共程序想要從這三個(gè)循環(huán)中出來(lái)，就需要執(zhí)行100*100*100次，也就是n的立方，所以這段代碼的時(shí)間復(fù)雜度是O(n^3)

1.4對(duì)數(shù)階

對(duì)數(shù)，屬于高中數(shù)學(xué)的內(nèi)容，我們分析程序以程序?yàn)橹?#xff0c;數(shù)學(xué)為輔，所以不用過(guò)分擔(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個(gè)2相乘后大于n，那么x個(gè)2相乘后就會(huì)退出循環(huán)。那么就有公式：2^x=n，得到x=log(2)n。所以這個(gè)循環(huán)的時(shí)間復(fù)雜度為O(logn)；

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

下面給出表和圖，可以體會(huì)一下增長(zhǎng)趨勢(shì)：

?

1.5常數(shù)階

一般不涉及循環(huán)操作的都是常數(shù)階，因?yàn)樗粫?huì)隨著n的增長(zhǎng)而增加操作次數(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來(lái)替換，所以上述代碼的時(shí)間復(fù)雜度為O(1)

1.6小結(jié)

下面是對(duì)常見時(shí)間復(fù)雜度的一個(gè)總結(jié)：

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

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

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

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

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

2.1幾個(gè)案例

?案例一：

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方法中，有一個(gè)for循環(huán)，循環(huán)體調(diào)用了show方法，由于show方法內(nèi)部只執(zhí)行了一行代碼，所以show的時(shí)間復(fù)雜度為O(1)，那main方法的時(shí)間復(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方法中，有一個(gè)for循環(huán)，循環(huán)體調(diào)用了show方法，由于show方法內(nèi)部也有一個(gè)for循環(huán)，所以show方法的時(shí)間復(fù)雜度為O(n)，那main方法的時(shí)間復(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方法中，有一個(gè)for循環(huán)，所以show方法的時(shí)間復(fù)雜度為o(n)，在main方法中，show(n)這行代碼內(nèi)部執(zhí)行的次數(shù)為n，第一個(gè)for循環(huán)內(nèi)調(diào)用了show方法，所以其執(zhí)行次數(shù)為n^2，第二個(gè)嵌套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保留最高階項(xiàng)，并去掉最高階項(xiàng)的常數(shù)因子2，所以最終main方法的時(shí)間復(fù)雜度為O(n^2)

2.2最壞情況

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

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

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

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

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

3.小結(jié)

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

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

?