算法的時間復(fù)雜度推導(dǎo)方法

獨(dú)立博客地址：chugang.net

語句頻度

語句頻度是指語句的重復(fù)執(zhí)行次數(shù)。

推導(dǎo)大O階方法

方法

1. 用常數(shù)1取代運(yùn)行時間中的所有加法常數(shù)。
2. 在修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高階項(xiàng)。
3. 如果最高階項(xiàng)存在且不是1，則去除與這個項(xiàng)相乘的乘數(shù)。

常數(shù)階舉例運(yùn)用

右側(cè)注釋中的 num 表示語句執(zhí)行的次數(shù)。

int sum = 0, n = 100;       /* num = 1 */
sum = (n+1) * n / 2;        /* num = 1 */
printf("%d", sum);          /* num = 1 */

這段代碼的運(yùn)行次數(shù)函數(shù)是 f(n) = 1 + 1 + 1 ，根據(jù)“推導(dǎo)大O階方法”中的第一條規(guī)則，把
1 + 1 + 1 用 1 替換，運(yùn)行次數(shù)函數(shù)變成了 f(n) = 1。該函數(shù)只有常數(shù)項(xiàng)，只需使用規(guī)
則1就可以推導(dǎo)出它即這段代碼的時間復(fù)雜度是 O(1) 。

假如 sum = (n+1) * n / 2 執(zhí)行3次，將上面的代碼修改為:

int sum = 0, n = 100;       /* num = 1 */
sum = (n+1) * n / 2;        /* num = 1 */
sum = (n+1) * n / 2;        /* num = 1 */
sum = (n+1) * n / 2;        /* num = 1 */
printf("%d", sum);          /* num = 1 */

這段代碼的運(yùn)行次數(shù)函數(shù)是 f(n) = 1 + 1 + 1 + 1 + 1 。 按照推導(dǎo)大O階第一條規(guī)則，用1取代
所有的加法常數(shù)，這段代碼的運(yùn)行次數(shù)函數(shù)是 f(n) = 1。這段代碼的時間復(fù)雜度依然是 f(n) = O(1) 。

所有這類代碼的時間復(fù)雜度都是 O(1)。O(1)叫做常數(shù)階。不存在 O(2) 、 O(9) 這類寫法。

線性階舉例運(yùn)用

code-3

int i;
for(i = 0; i < n; i++){
    // 時間復(fù)雜度為O(1)的代碼
}

code-3的運(yùn)行次數(shù)函數(shù)是 f(n) = n * 1。加法常數(shù)為0個，跳過規(guī)則一。變量n的最高階是 n * 1，無
其他項(xiàng)，跳過規(guī)則二。n * 1中的系數(shù)本來就是1，也可以直接跳過規(guī)則三，得到code-3的時間復(fù)雜度是
f(n) = O(n)。

code-4

int i;
for(i = 0; i < n; i++){
    // 時間復(fù)雜度為O(1)的代碼
}

int j;
for(j = 0; j < m; j++){
    // 時間復(fù)雜度為O(1)的代碼
}

code-4的運(yùn)行次數(shù)函數(shù)是f(n) = n * 1 + m * 1。直接跳過規(guī)則一。n * 1 + m * 1有兩個變量，
但次數(shù)都是1，任何一項(xiàng) n * 1 或 m * 1 都可視為最高價，根據(jù)推導(dǎo)規(guī)則二“保留最高階”，得出
運(yùn)行次數(shù)函數(shù)是f(n) = n * 1 或 f(n) = m * 1。最后根據(jù)規(guī)則三，得出code-4的時間復(fù)雜度是
f(n) = O(n)。

對數(shù)階舉例運(yùn)用

code-5

int count = 1;
while(count < n){
    count = count * 2;
    //其他時間復(fù)雜度為O(1)的代碼 
}

code-5似乎不能用前面的推導(dǎo)大O階方法來分析時間復(fù)雜度，我從《數(shù)據(jù)結(jié)構(gòu)與算法分析》P21找到了分析
"運(yùn)行時間中的對數(shù)"的一般法則。這個一般法則是：

如果一個算法用常數(shù)時間(O(1)將問題的大小削減為其一部分（通常是1/2），那么該算法就是 O(log N)。
另一方面，如果使用常數(shù)時間只是把問題減少一個常數(shù)（如將問題減少1），那么這種算法就是 O(N) 。

code-5中，假設(shè) n = 8 ，初始化時，while(count < n) 需要運(yùn)行8次。經(jīng)過一次循環(huán)后，count變?yōu)?，
循環(huán)需要運(yùn)行4次，變?yōu)樵瓉淼囊话?。根?jù)那條一般法則，判斷 code-5 的時間復(fù)雜度是 O(log N)。

將code-5修改為code-6，

int count = 1;
while(count < n){
    count = count + 2;
    //其他時間復(fù)雜度為O(1)的代碼 
}

code-6每次執(zhí)行循環(huán)后，會把問題減少2個常數(shù)，時間復(fù)雜度應(yīng)為 O(N)。

若將code-6中的count = count + 2改為code = count - 2，時間復(fù)雜度仍然是 O(N)。但我有點(diǎn)理解不了。

平方價舉例運(yùn)用

code-7

int i, j;   /*1*/
for(i = 0; i < n; i++){ /*2*/
    for(j = 0; j < n; j++){ /*3*/
        //時間復(fù)雜度為O(1)的代碼 /*4*/
    }   /*5*/
}   /*6*/

code-7中第二個循環(huán)體的時間復(fù)雜度是O(N)。第一個循環(huán)體將第二個循環(huán)體再執(zhí)行N次，時間復(fù)雜度變?yōu)?code>O(N2)。
如果將第二個循環(huán)體中的n改為m，那么code-7的時間復(fù)雜度就是O(N*M)。注意，O(N*M)和O(N2)都叫做
平方階，二者實(shí)質(zhì)相同。

多層循環(huán)體的時間復(fù)雜度就是每層循環(huán)體的運(yùn)行次數(shù)相乘。

code-8

int i, j;
for(i = 0; i < n; i++){
    for(j = i; j < n; j++){
        //時間復(fù)雜度為O(1)的代碼
    }
}

code-8運(yùn)行次數(shù)是(n+1)*n*n/2。只保留最高階并且去掉它的系數(shù)，時間復(fù)雜度是O(N2)。有些地方理解不了。

code-9

void function(int count){

    int j;
    
    for(j = count; j < n; j++){
    
        printf("%s", "hello,world");
        
    }
}

n++;        /* num = 1 */

function(n);    /* num = n */

int i,j;    /* num = 1 */

for(i = 0; i < n; i++){     /* num = n*n */
    
    function(i);
    
}

for(i = 0; i < n; i++){         /* num = (n+1)*n/2 */
    
    for(j = i; j < n; j++){
        
        printf("%s", "hi");
        
    }
}

code-9的時間復(fù)雜度是多少呢？

首先將每行代碼的執(zhí)行次數(shù)標(biāo)出來。

code-9的執(zhí)行次數(shù)（首先忽略掉常數(shù)項(xiàng)）是n + n*n + (n+1)*n/2，計算結(jié)果為1.5*n*n + 2*n。
只保留最高階1.5*n*n，最后將系數(shù)變?yōu)?，執(zhí)行次數(shù)為n*n，時間復(fù)雜度為O(N2)。

這種方法有不確定性的因素存在，或者說，在計算執(zhí)行次數(shù)的時候，使用了互相矛盾的方法。

獨(dú)立博客地址：chugang.net

重新思考之后，發(fā)現(xiàn)并不存在矛盾，而是《大話數(shù)據(jù)結(jié)構(gòu)》中推導(dǎo)時間復(fù)雜度的方法有小缺陷。這個推導(dǎo)
本身就是一種粗略估計，為何在推導(dǎo)過程中有時又在進(jìn)行精確計算呢？以code-8為例，該書使用了精確
的計算方法。若全部都堅持使用粗略估計計算，那么計算過程是這樣的：code-8中第二個循環(huán)體的運(yùn)行
次數(shù)是N，或者抽象為“一個變量”，第一個循環(huán)體的運(yùn)行次數(shù)也是N或M，也抽象為“一個變量”，整體的運(yùn)行
次數(shù)為兩個變量相乘，即時間復(fù)雜度為O(N2)。這種粗略估計計算方法，建立的基礎(chǔ)是：影響循環(huán)執(zhí)行次數(shù)
的變量只有那個與循環(huán)終止條件相關(guān)的變量，與起始變量無關(guān)。

這種方法，又不能適用于對數(shù)階的時間復(fù)雜度推導(dǎo)?；蛟S，對數(shù)階中的循環(huán)，本來就是一種特殊情況，不能
采用普通循環(huán)的推導(dǎo)方法。此處存疑。*

常見的時間復(fù)雜度

直接摘抄《大話數(shù)據(jù)結(jié)構(gòu)》中的有關(guān)部分。

常見的時間復(fù)雜度

理解不了這些時間復(fù)雜度所耗時間的順序，應(yīng)該如何比較它們所耗時間？

獨(dú)立博客地址：chugang.net