如何使用c++來(lái)進(jìn)行算法分析

這期內(nèi)容當(dāng)中小編將會(huì)給大家?guī)?lái)有關(guān)如何使用c++來(lái)進(jìn)行算法分析，文章內(nèi)容豐富且以專(zhuān)業(yè)的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。

• 時(shí)間復(fù)雜度

O(1) < O(logn) < O(n) < O(n^2) < O(n^C) < O(C^n)
常數(shù) < 對(duì)數(shù)階 < 線(xiàn)性階 < 平方階 < 多項(xiàng)式階 < 指數(shù)階

•  常數(shù)階

void aFunction(){  
     int c =  10 +  20;

    int d = c * c;  printf(d);

}

分析：計(jì)算量為2,2為常數(shù)函數(shù)的增長(zhǎng)影響不大所以記為O(1);

• 線(xiàn)性階

void bFunction(int n){

    for(   int i =   0;i < n;i++){   // n  

        int c =   2 * i;   // 1  

        int d =   3 * i;   // 2  

    }

}

 分析： 函數(shù)的計(jì)算量等于(n)(2) ,2常數(shù)可以忽略不計(jì)所以記為O(n)

• 平方階

void bFunction(int n){

    for(   int i =   0;i < n;i++){

        for(   int j =   0;j < i;j++){

         }

     }

}

分析： 整個(gè)函數(shù)的計(jì)算量為(n)(n-1) ，常數(shù)量忽略不計(jì)所以記做O(n^2)

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

void bFunction(int n){

    for( int i = 3;i < n;){

             i *= 3; }

}

分析：假設(shè)循環(huán)s次 循環(huán)條件為 s = 3^s < n; 用對(duì)數(shù)表示為 s = log3n ，記做 O(log3n) ，常數(shù)可忽略 O(logn)  

• 多項(xiàng)數(shù)階 

void bFunction(int n){

    for(       int i =       0;i < n;i++){

        for(       int j =       0;j < n;j++){

            for(       int k =       0;k < n;k++){

             }

         }

     }

}

分析：計(jì)算量為n^3,次冪為常數(shù)記做為O(n^C)

• 指數(shù)階 

void bFunction(int n){

    int num = n;

    for( int i = 0;i < n;i++){ //O(n)          

         num *= n;

     }

    for ( int j = 0;j<num;j++){ //O(n)          

     }

}

分析： 函數(shù)輸入的參數(shù)n將作為num的次冪,假設(shè)循環(huán)次數(shù)為s, s = 2n,那么時(shí)間復(fù)雜度為O(2 n) 可記為O(C^n)          

• 算法分析中的常見(jiàn)函數(shù) 

上述就是小編為大家分享的如何使用c++來(lái)進(jìn)行算法分析了，如果剛好有類(lèi)似的疑惑，不妨參照上述分析進(jìn)行理解。如果想知道更多相關(guān)知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道。