不可一日無煙卷

    在比較算法的效率時，往往是算法的運(yùn)行時間與數(shù)據(jù)項個數(shù)關(guān)系間比較，例如，為了得到某個結(jié)果，在同一數(shù)據(jù)量下，哪個算法運(yùn)行最快，效率最高，而后改變這一數(shù)據(jù)量，哪種算法的時間又最快......

大O表示法
    在描述算法運(yùn)行時間時，往往能看到O(N)、O(logN)等，大O中的O的意思就是"order of"（大約是），它是種概念，就比如 大型車、小型車和中型車，忽略具體大小尺寸，來描述汽車。

首先來跟著我分析一段代碼：
示例 1:

這個程序是計算 Σⁿ _i=1 i³ 即 從1開始到n的整數(shù)，計算它們的立方和

    聲明不計時間，賦值、計算、比較每次占一個時間單位，則從第四行開始，首先花費(fèi)1個時間單位，接著進(jìn)入循環(huán)，給i賦值，又占一個單位，它只運(yùn)行一次，接著比較，運(yùn)行n+1次，i++為兩次計算，一次加一，一次賦值，而它要運(yùn)行n次，占2n個時間單位，循環(huán)主體是四個時間單位（兩個乘法，一個加法，一個賦值），總共執(zhí)行n次，故花費(fèi)4n個單位，最后返回花費(fèi)1個時間單位。

    最終，這個程序總共花費(fèi)1(賦值)+1(賦值)+(1+2n)(比較)+4n(計算)+1(返回)=6n+4 個時間單位，但是，如果每個程序都像這樣計算的話，豈不是讓人崩潰，大O表示法的宗旨就是，舍去所有常量，把它歸入cpu，平臺等因素造成的時間，假設(shè)這些常量總體為K，則上面那個程序所花費(fèi)的時間是n+K，按照這種計算方式，每個程序的運(yùn)行時間都會轉(zhuǎn)化為xn+K，所以我們可以把K舍去。

    最終，以大O表示法，這個程序的運(yùn)行時間是O(N)。

    如果是一個嵌套循環(huán)呢，比如：
示例 2:

這段代碼的運(yùn)行時間就為O(N²)了 (自己按照上面那種方法掐指算一下)。

    如果把實例2添加進(jìn)示例1中的返回語句前，則運(yùn)行時間為n+n²，以大O表示法則為O(n²)。

    看到了吧，大O表示法是沒有加號的，所有這些都被忽略了，沒有常數(shù)，只有迭代次數(shù)。

    很多與我一樣數(shù)學(xué)底子不好的同學(xué)，遇到O(logN)等這樣帶對數(shù)的時候就會迷茫，其實也不難，拿二分搜索舉例，它的運(yùn)行時間是O(logN)。

    什么是二分搜索？我來舉個例子，李詠大哥讓你猜個電器的價格，猜中了就歸你了，如果你聰明的話，就不會亂猜，你會首先隨機(jī)猜一個自己認(rèn)為適合的價格(比如一個電視，你猜5000)，如果他喊低了，就繼續(xù)往上加，但是他喊高了，你會選擇剛才價格的一半(2500)，如果他喊高了，則繼續(xù)折一半(1250），這次他喊低了，你就猜3750，按照這種原則，你最終猜對了，是3750，你只用了3次。

    按照這種方法，最壞的情況下(即猜的次數(shù)最多)，N個數(shù)所用的次數(shù)X<=log₂N ，因為2^x<=n，比如10個數(shù)，最多猜測3次，即2³<=10 ，3<=log₂10 。
    
    現(xiàn)在大致明白了log形式的運(yùn)行時間了吧。

    這里列出一些運(yùn)行時間計算的一些法則，是從《數(shù)據(jù)結(jié)構(gòu)與算法分析C++描述(第三版)》上面摘錄的

法則1：for循環(huán)  一個for循環(huán)的運(yùn)行時間至多是該for循環(huán)內(nèi)語句(包括測試)的運(yùn)行時間乘以迭代的次數(shù)。

法則2：嵌套循環(huán)  從里向外分析這些循環(huán)。在一組嵌套循環(huán)內(nèi)部的一條語句總的運(yùn)行時間為該語句的運(yùn)行時間乘以該組所有循環(huán)的大小的乘積。

法則3：順序語句  將各個語句的運(yùn)行時間求和即可（這意味著，其中的最大值就是所得的運(yùn)行時間）。

法則4：IF/ELSE語句  一個if/else語句的運(yùn)行時間從不超過判斷再加上每個主體中運(yùn)行時間較長者的總的運(yùn)行時間。

    最后，總結(jié)一下，其實運(yùn)行時間O就是相對增長率，我們所比較的運(yùn)行時間，就是把他們的相對增長率進(jìn)行比較，這里的運(yùn)行時間，都是在最壞情況下得出的，因為數(shù)據(jù)量充滿不確定性，不保守估計的話，會出錯，了解了運(yùn)行時間的算法，對一個算法的好壞的判斷就有基準(zhǔn)了，以后會用到這里（尤其是排序算法）。

    我所理解的很可能有錯誤，希望高手拍磚指正，謝絕打擊的言論，畢竟我不懂高數(shù)，這個設(shè)計到了極限。


ps:我們當(dāng)時排序算法就只教了冒泡，就連快速排序都不知道是什么，現(xiàn)在同學(xué)們遇到排序，都是冒泡
還好，我學(xué)了比較多的排序算法，每個都有自己的應(yīng)用場景，我以后的筆記會討論排序的，真希望我的同學(xué)們能看看這些筆記。