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;
        }
    }
}

复杂度计算-

Loop#2 复杂度- O( ln(i) )，当每个时间数都可以被 2 整除，最终达到 1 时，就会出现这种情况。

Loop#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

意味着，阶乘（N）与（N）^（3N/2）成正比

由上式，

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

C = O(T ln(T) ).

问题-

  1. 我们可以用 N 来表示 T 吗？
  2. 如果是，那么请帮我转换它。
4

1 回答 1

2

您尝试查找的数字称为5-smooth。维基百科文章中的一个界限表明有 O(log^3 T) 5-平滑数字小于 T，所以给定 N，我们需要设置 T = 2^Omega(N^(1/3) ）。

如果您尝试枚举 5 个平滑数字，Dijkstra 的算法可能是要走的路，在 O(N) 时间内返回 N 个数字。

于 2016-02-29T14:58:44.743 回答