1、復(fù)雜度分析

復(fù)雜度分析本身是非常理論化的一個內(nèi)容，在計算機科學(xué)中，有一個專門的學(xué)科叫做——計算復(fù)雜性理論。

很多童鞋看過《算法導(dǎo)論》，這本書的內(nèi)容很多很強調(diào)算法導(dǎo)論。

但是實際上，對于普通程序員來說，不需要過度強調(diào)理論化的內(nèi)容。因為工作中更多面對的是實際的
軟件工程，工程化的工作不需要面對太多理論性的東東。

2、復(fù)雜度分析

復(fù)雜度分析的作用：是為了表示算法的性能。

對于同樣一個任務(wù)，可能有多個實現(xiàn)方式，即多個算法。這些不同的算法，它們的時間性能是否有差異呢？

我們雖然可以用一個測試用例，或者一組測試用例實際比較性能差異。
但是，這樣的比較結(jié)果有局限性。

比如，需要保證運行不同算法的計算機硬件設(shè)備的性能一致，甚至深入的說，他們的OS當(dāng)時的狀態(tài)都需要是一致的。
這本身很難保證，而且測試結(jié)果也與我們的測試用例設(shè)計和用例輸入相關(guān)。

而且，最重要的是這樣比較是事后的。

如何突破局限性，如何事前比較呢？
種種這樣的需求，都需要我們有一套工具，從數(shù)學(xué)的層面，用抽象的方式，判斷一個算法的性能是怎樣的？

為了回應(yīng)這樣的需求，就產(chǎn)生了復(fù)雜度分析這樣一個概念。

3、復(fù)雜度分析和算法性能的關(guān)系

復(fù)雜度分析，如何表示算法的性能呢？

需要注意的是，算法復(fù)雜度分析通?？紤]最壞的情況。

這樣的思想非常普遍，比如上班時，為了不遲到，考慮最長需要多少時間，甚至將堵車的時間都考慮進去。

即，復(fù)雜度分析，表示的是算法運行的上界。

對于我們的線性查找法代碼，我們來進行一個復(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;
}

具體的分析過程如下：
n = data.length
T 表示時間
T和n的關(guān)系到底是怎樣的？
T = n?n個元素全部掃描了一遍？ 就是n？
T = 2n？if里有比較、有返回結(jié)果這2步 就是2n？
T = 3n？ 其實if中的data[i]，要在數(shù)組data中找到i這個元素，是一步尋址，也需要算作一個子步驟。 3n了？
T = 4n？for循環(huán)中也包含每次要做的事情，i<data.length,也是一個判斷操作，所以4n？

T = 5n？for循環(huán)中還有一個i++的操作，所以5n?
T = 5n+2？ int i =0;加1次，return -1；加1次，所T=5n+2？
……

其實，再繼續(xù)分析下去還可以分析出很多可能，就不繼續(xù)分析了，為什么不繼續(xù)了呢？

因為真的分析的話，拿出for循環(huán)對應(yīng)的匯編代碼，看看這個循環(huán)執(zhí)行了多少指令？

可是拿出匯編代碼也不夠，因為匯編代碼對應(yīng)著機器指令，而機器指令不僅僅是代碼有多少行而已，
還要追溯到運行代碼的CPU架構(gòu)上，有些復(fù)雜指令在有些CPU上，就一個指令，但在另外一些CPU上，可能就是多個指令。

對于上層應(yīng)用軟件開發(fā)者來說，分析清楚每一行高級語言代碼對應(yīng)著多少機器指令，是一件非常困難，甚至說不可能的事情，其實也沒有必要。

而且即便T=5n+2，那這個等式的時間單位是多少呢？是毫秒ms嘛？肯定不對應(yīng)時間，對應(yīng)的是指令數(shù)，但是一條指令在cpu中執(zhí)行多久我們知道嘛？

我們不知道。

所以，這些其實我們都不需要考慮，我們需要進行一個化簡。這也是計算機科學(xué)家們定義復(fù)雜度分析這個概念時做過的事兒，沒錯，他們做了化簡。

我們不需要知道執(zhí)行這樣一個循環(huán)，對這n個元素操作，每一次循環(huán)需要執(zhí)行多少個指令；
我們只需要知道，整個算法和這個data數(shù)組的大小，和這個數(shù)據(jù)規(guī)模n成一個正比的關(guān)系即可。

4、O(n)

這個就記作O(n)，表示的就是運行時間和數(shù)據(jù)規(guī)模n之間的一個正比關(guān)系。
進一步看，如果：
T = c1*n + c2
這個算法我們就可以記作O(n)，即常數(shù)c1、c2都被我們忽略掉了，即算法復(fù)雜度的世界中，常數(shù)不重要。

5、復(fù)雜度描述的是什么？

復(fù)雜度描述的是：隨著數(shù)據(jù)規(guī)模的增大，算法性能的變化趨勢。

假設(shè)有2個算法，分別是T1和T2，它們的詳細情況如下：

T1 = 10000n
T2 = 2n2
第一個算法 O(n)級別的算法，第二個算法O(n2)級別的算法。
從復(fù)雜度理論的角度來看，第一個算法優(yōu)于第二個算法。

**因為總是會存在某一臨界點n0，當(dāng)n>n0,T1<T2。
可以計算出，這里的臨界點n0為5000。
一旦數(shù)據(jù)規(guī)模大于5000，算法一的性能優(yōu)勢就體現(xiàn)出來了，而且n越大，體現(xiàn)的越明顯。

所以O(shè)(n)描述的就是隨著n的變化，算法的性能的變化趨勢，

而不是說n取某個值時，算法的性能。

實際上，如果測試數(shù)據(jù)小于5000，比如為100時，第二個算法O(n2)反而優(yōu)于第一個算法O(n)；

但是評價算法性能，我們要看n逐漸上漲的情況，甚至看n無窮大的情況。文章來源地址http://www.zghlxwxcb.cn/news/detail-417839.html

到了這里，關(guān)于扎實打牢數(shù)據(jù)結(jié)構(gòu)算法根基，從此不怕算法面試系列之007 week01 02-07 簡單的復(fù)雜度分析的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！