1、線性查找法的復(fù)雜度

public static <E> int search(E [] data,E target){
    for (int i = 0; i < data.length; i++)
        if (data[i].equals(target))
            return i;
    return -1;
}

很容易看出，這個(gè)算法的復(fù)雜度為 O(n)。

2、一個(gè)數(shù)組中的元素可以兩兩組成哪些數(shù)據(jù)對(duì)？ O(n2)

需要實(shí)現(xiàn)一個(gè)算法，這個(gè)算法用于：找到一個(gè)數(shù)組中的元素可以兩兩組成哪些數(shù)據(jù)對(duì)？
①、在不要求順序的情況下，即data[i],data[j]和data[j],data[i]看作同一個(gè)數(shù)據(jù)對(duì)；
②、每一個(gè)元素自己和自己不能組成數(shù)據(jù)對(duì)，即data[i],data[i]不是數(shù)據(jù)對(duì)。

這個(gè)算法的代碼如下：

  for(int i=0;i<data.length;i++)
    for (int j=i+1; j< data.length;j++) 
        //獲得一個(gè)數(shù)據(jù)對(duì) (data[i],data[j])

注意，j從i+1開始。
可以分析得出，這個(gè)算法的復(fù)雜度為O(n2)。

雖然是2重循環(huán)，但是循環(huán)執(zhí)行的次數(shù)并不是nn，其實(shí)執(zhí)行的次數(shù)為1/2n2，但是1/2作為常數(shù)，不重要。

3、遍歷一個(gè)n*n的二維數(shù)組 O(n2)

我們來實(shí)現(xiàn)一個(gè)需求：遍歷一個(gè)n*n的二維數(shù)組 ，代碼如下：

for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) 
        //遍歷到A[i][j]

上述代碼的時(shí)間復(fù)雜度是O(n2)。
注：

在做復(fù)雜度分析時(shí)，一定要明確n是誰？

假設(shè)遍歷一個(gè)aa的二維數(shù)組 O(a2)=O(n)；
而 aa=n，上面的n表示的是維度為n（每一個(gè)維度的元素個(gè)數(shù)都是n），下面的n表示的是元素總數(shù)為n。

 for (int i = 0; i < a; i++)
    for (int j = 0; j < a; j++) 
        //遍歷到A[i][j]

看時(shí)間復(fù)雜度也好，總結(jié)時(shí)間復(fù)雜度也好，一定一定要明確n到底誰？

4、數(shù)字n的二進(jìn)制位數(shù) O(logn)

我們來實(shí)現(xiàn)一個(gè)需求：求解數(shù)字n的二進(jìn)制位的位數(shù)？
如何理解位數(shù)，我們來舉個(gè)例子，一看就懂：
16這個(gè)數(shù)字的10進(jìn)制位數(shù)有幾位？
有2位嘛，1和16

520這個(gè)數(shù)字的10進(jìn)制位數(shù)有幾位？
3位嘛，5、2、0

我們看下這個(gè)算法的實(shí)現(xiàn)的偽碼：

while(n){
    n%2 //n的二進(jìn)制中的一位
    n/=2;
}

上面?zhèn)未a的時(shí)間復(fù)雜度是：O(logn)。

不同的底數(shù)相差的只是一個(gè)常數(shù)而已，可以復(fù)習(xí)下高中數(shù)學(xué)的換底公式；

所以，最終我們對(duì)數(shù)復(fù)雜度都是不關(guān)注底數(shù)的，都是O(logn)。

注意，分析算法復(fù)雜度的時(shí)候，也不能只看循環(huán)個(gè)數(shù)。

這里n每次除以2，而不是每次減1，所以它到0的速度非?？臁圆皇荗(n)級(jí)別，而是O(logn)級(jí)別。

5、求解數(shù)字N的所有約數(shù)？ O(n)、O(√n) ：根號(hào)n

我們來實(shí)現(xiàn)一個(gè)需求：我們來實(shí)現(xiàn)一個(gè)需求。
首先需要回顧下約數(shù)的概念，假設(shè)a是n的約數(shù)，表示n除以a沒有余數(shù)，即n可以整除a。

for (int i = 1; i <= n ; i++)
    if (n%i==0)
        // i是n的一個(gè)約數(shù)

接著，我們來對(duì)上述算法做一個(gè)優(yōu)化：

 for (int i = 1; i*i <= n ; i++)
    if (n%i==0) //i和n/i都是n的約數(shù)，同時(shí)找到兩個(gè)約數(shù)（需要排除i=n/i的情況）

再次強(qiáng)調(diào)，看算法復(fù)雜度，不能看循環(huán)個(gè)數(shù)。
上述兩個(gè)算法都是一重循環(huán)，但他們循環(huán)的結(jié)束條件不同，優(yōu)化前的算法是i<=n，優(yōu)化后的是i*i<n，所以實(shí)際上這兩個(gè)算法的執(zhí)行次數(shù)是非常不同的。
一個(gè)是n，一個(gè)是根號(hào)n。

所以這個(gè)算法的實(shí)現(xiàn)，有2種復(fù)雜度：
O(n)和O(√n) ：根號(hào)n。。

6、求所有長度位n的二進(jìn)制數(shù)字的個(gè)數(shù)？ O(2^n)；2的n次方

我們來實(shí)現(xiàn)一個(gè)需求：求所有長度位n的二進(jìn)制數(shù)字的個(gè)數(shù)？

如何理解這個(gè)題目，比如，所有長度位3的二進(jìn)制數(shù)字，一共有幾個(gè)？

一共有8個(gè)，分別是從0到7
0、1、10、11、100、101、110、111

比如，所有長度位4的二進(jìn)制數(shù)字。
一共有16個(gè)，分別是從0到15
0、1、10、11、100、101、110、111
1000、1001、1010、1011、1100、1101、1110、1111

這里我們就是用排列組合來得到，長度為n，相當(dāng)于有n個(gè)位置，每個(gè)位置或者填0，或者填1；
每個(gè)位置有2種選擇，現(xiàn)在有n個(gè)位置，則相當(dāng)于n個(gè)2連續(xù)乘起來
222……222=2^n，是2的n次方。

所以，這個(gè)算法的復(fù)雜度為：O(2^n)，是2的n次方。

7、長度為n的數(shù)組的所有排列 O(n!)

我們來是實(shí)現(xiàn)一個(gè)需求，求解長度為n的數(shù)組的所有排列個(gè)數(shù)。

舉個(gè)例子，比如，1、2、3的排列個(gè)數(shù)為6，
1、2、3、4的排列個(gè)數(shù)為24。
這里用到了數(shù)學(xué)中的全排列公式。

全排列個(gè)數(shù)，n??；
所以這個(gè)算法的復(fù)雜度為：O(n!)。

O(2^n)，n次方復(fù)雜度和 O(n!)階乘復(fù)雜度，都是非常高，性能非常差的復(fù)雜度。。

O(2^n)，當(dāng)n為10，基本就是1000了，程序員都熟悉，實(shí)際是1024，
當(dāng)n為20，基本就是1000*1000=100w了，普通程序員都期望追求的年薪數(shù)字是吧哈哈
當(dāng)n為20，基本就是10億了，你的10個(gè)小目標(biāo)？這么小的目標(biāo)，MosesMin可不敢有，哈哈哈
甚至當(dāng)n為100時(shí)，科學(xué)家統(tǒng)計(jì)，它的大小就接近于宇宙中所有原子的個(gè)數(shù)那么多個(gè)了……
所以指數(shù)級(jí)別是一個(gè)非?？植赖脑鲩L。

通常，算法設(shè)計(jì)上，如果n<=20，可以考慮指數(shù)級(jí)別的復(fù)雜度；如果n>20，指數(shù)級(jí)別的復(fù)雜度是承受不起的。
所以算法設(shè)計(jì)上，要盡可能避免指數(shù)級(jí)別的復(fù)雜度；
而階乘的復(fù)雜度就更高了，更是需要全力避免。
階乘級(jí)別也一樣，n<20可以考慮，大于20就不能考慮了。

8、判斷n是否是偶數(shù)？ O(1)

判斷n是否是偶數(shù)？偽碼如下：

return n%2 == 0

只有一行代碼，所以復(fù)雜度為：O(1)。

9、常見算法復(fù)雜度總結(jié)

結(jié)論很重要，要記?。?br> O(1)<O(logn)<O(√n)<O(n)<O(nlogn)<O(n2)<O(2^n)<O(n!)

注意；
O(nlogn)很重要。

O(logn)<O(√n)如何比較，不做數(shù)學(xué)推導(dǎo)了，舉個(gè)例子記一下：
log以2為底的1000是多少，大概是10，因?yàn)?的10次方是1024嘛，所以log以2為底的1000大概是10；
1000的根號(hào)值是30多，因?yàn)?0*30=900嘛，所以大概是30。
10<30,所以我們這樣記得：O(logn)<O(√n)

logn比n快很多。
n取100w，logn大概是20次左右，而n要100w次；
數(shù)據(jù)規(guī)模100w的時(shí)候，n和logn的性能差距在5w倍。

logn和nlogn這樣的算法，會(huì)非常多，需要學(xué)習(xí)。
空間復(fù)雜度和時(shí)間復(fù)雜度的計(jì)算基本差不多。

時(shí)間更值錢，空間不太值錢；
所以算法設(shè)計(jì)更重視時(shí)間復(fù)雜度，所以很多算法設(shè)計(jì)思想的本質(zhì)更多是以空間換時(shí)間。
即：可不可以考慮使用緩存等等.

我們常見算法的復(fù)雜度梳理就到這里。文章來源地址http://www.zghlxwxcb.cn/news/detail-418674.html

到了這里，關(guān)于扎實(shí)打牢數(shù)據(jù)結(jié)構(gòu)算法根基，從此不怕算法面試系列之008 week01 02-08 通過常見算法，對(duì)常見的時(shí)間復(fù)雜度做梳理的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！