2

問題 - 2、3、5 でしか割り切れない最初の N 個の数を見つける複雑さは?

私の努力

コード -

void printFirstNNumbers(int N) {

    int numbersFound = 0;

    // loop#1
    for(int cnt = 0; ; cnt++) {
        int currentNumber = cnt;

        // loop#2
        while(currentNumber != 1) {
            if(currenNumber%2 == 0) currentNumber /= 2;
            else if(currentNumber%3 == 0) currentNumber /= 3;
            else if(currentNumber%5 == 0) currentNumber /= 5;
            else break;
        }

        if(currentNumber == 1) {
            cout << currentNumber;
            numbersFound++;
            if(numbersFound == N) return;
        }
    }
}

複雑さの計算-

ループ 2 の複雑さ- O( ln(i) )、これは、数値が 2 で割り切れるたびに発生し、最終的に 1 に達します。

ループ 1 の複雑さ- O(T)、ここで T は、最初の N 個の数値を取得するために反復する回数です。

したがって、複雑さは ln(i) の合計です。ここで、i = 2 から T です。

C = summation of ln(i), where i = 2 to T.

2^C = 2*3*....T = factorial(T)

C = ln( factorial(T) )

where factorial(N) = sqrt(2*pie*N)* (N/e)^N

factorial(N) は (N)^(3N/2) に正比例することを意味します

上式により、

C = ln ( (T)^(3T/2) ) = (3T/2) ln(T)

C = O(T ln(T) ).

質問-

  1. T を N で表すことはできますか?
  2. はいの場合は、それを変換するのを手伝ってください。
4

1 に答える 1

2

見つけようとしている数字は5-smoothと呼ばれます。ウィキペディアの記事の境界の 1 つは、T よりも小さい O(log^3 T) 5-smooth 数があることを示唆しているため、N を指定すると、T = 2^Omega(N^(1/3) と設定する必要があります。 ）。

5-smooth 数値を列挙しようとしている場合は、おそらく O(N) 時間で N 個の数値を返すDijkstra のアルゴリズムが適しています。

于 2016-02-29T14:58:44.743 に答える