0

友人が彼のアルゴリズムの複雑さを分析するのを手伝おうとしていますが、Big-O 記法についての私の理解はかなり限られています。

コードは次のようになります。

int SAMPLES = 2000;
int K_SAMPLES = 5000;

int i = 0; // initial index position    
while (i < SAMPLES)
{
    enumerate();                       // Complexity: O(SAMPLES)
    int neighbors = find_neighbors(i); // Complexity: O(1) 

    // Worst case scenario, neighbors is the same number of SAMPLES
    int f = 0;
    while (f < neighbors) // This loop is probably O(SAMPLES) as well.
    {
        int k = 0; // counter variable
        while (k < K_SAMPLES) // Not sure how to express the complexity of this loop.
        {                     // Worst case scenario K_SAMPLES might be bigger than SAMPLES. 

            // do something!

            k++;
        }
        f++;
    }

    i++;
}

コード内には 2 つの関数がありますが、単純なため複雑さを特定できました。ただし、内側のwhileループの複雑さを表現することはできませんでしたが、測定した後でも、これらすべての複雑さをアルゴリズムの計算の複雑さを表す式にまとめるには、まだ助けが必要です。

この件に関して真剣に助けが必要です。ありがとう！

4

2 に答える 2

3

最も内側のループから最も外側のループに向かう最悪のケースの分析 ( 「=」記号の軽度の乱用):

->  O(K_SAMPLES)                    -- complexity of just the k-loop

->  neighbors * O(K_SAMPLES)         -- complexity of f-loop accounted for
 =  SAMPLES * O(K_SAMPLES)          -- since neighbors = SAMPLES in worst case
 =  O(SAMPLES * K_SAMPLES)

->  O(SAMPLES) + O(SAMPLES * K_SAMPLES)  -- adding complexity of enumerate()
 =  O(SAMPLES + SAMPLES * K_SAMPLES)
 =  O(SAMPLES * K_SAMPLES)

漸近的に速く成長するため、SAMPLES用語は削除されました。SAMPLES * K_SAMPLESより正式には、

When C >= 2, SAMPLES >= 1, K_SAMPLES >= 1 then

SAMPLES + SAMPLES * K_SAMPLES  <=  C(SAMPLES * K_SAMPLES)
SAMPLES * (K_SAMPLES + 1)  <=  SAMPLES * C * K_SAMPLES
K_SAMPLES + 1  <=  C * K_SAMPLES

複数の変数を持つ big-O の詳細については、こちらを参照してください。最後のループを続けます。

->  SAMPLES * O(SAMPLES * K_SAMPLES)    -- complexity of i-loop accounted for
 =  O(SAMPLES^2 * K_SAMPLES)

によって返される平均数に応じてfind_neighbors(i)、平均 big-O が異なる場合があることに注意してください。

于 2013-03-06T06:39:11.897 に答える