确定整数因子分解算法的复杂度

Question

我开始学习计算复杂性、大O符号等知识，我被要求编写一个整数分解算法并确定它的复杂度。我已经编写了算法并且它可以工作，但是我在计算复杂度时遇到了困难。伪代码如下:

DEF fact (INT n)
BEGIN
    INT i

    FOR (i -> 2 TO i <= n / i STEP 1)
    DO
        WHILE ((n MOD i) = 0)
        DO
            PRINT("%int X", i)
            n -> n / i
        DONE
    DONE

    IF (n > 1)
    THEN
        PRINT("%int", n)

END

我尝试的做法非常错误：

f(x) = n-1 + n-1 + 1 + 1 = 2n

所以

f(n) = O(n)

我认为这是错误的，因为分解算法应该是计算上困难的，甚至不能是多项式。你有什么建议可以帮助我吗？也许我只是太累了，在这个深夜时间弄得一团糟 :(

提前感谢您。

- Ricardo Ferreira

Answer 1

这种现象被称为伪多项式性：复杂度看起来是多项式的，但实际上并不是。如果你想知道某个复杂度（这里是n）是否是多项式的，你必须看它与输入规模的关系。在大多数情况下，例如排序（例如合并排序可以在O(n lg n)中解决），n描述了输入的大小（元素数量）。然而，在这种情况下，n并不描述输入的大小；它就是输入值。那么，n的大小是多少？自然的选择应该是n中位数的数量，大约是lg n。因此，让w = lg n成为n的大小。现在我们看到O(n) = O(2^(lg n)) = O(2^w) - 换句话说，它是输入规模w的指数级别。

（请注意，O(n) = O(2^(lg n)) = O(2^w) 总是成立的；问题在于输入的大小是由n还是w = lg n描述的。此外，如果n描述列表中元素的数量，则严格来说应该计算列表中每个单独元素的位数以获得总输入大小；但通常假设在列表中，所有数字都被限制在某个大小范围内（例如32位）。）

- Aasmund Eldhuset

---

好的解释！然而，如果我们假设对n的操作不是原子步骤，而是依赖于n的大小w，则我们还需要考虑取模和除法都不是常数，而是在O(w ln w ...)中，因此整个算法的最坏情况复杂度不能是O(2^w)。 - le_m

Answer 2

利用你的递归算法。如果f(x)是分解所需操作数，n是找到的第一个因子，则f(x)=(n-1)+f(x/n)。对于任何分解算法来说，最坏情况是质数，此时算法的复杂度为O(n)。

分解算法之所以“难”主要是因为它们用于极大的数字。

- Tauf

---

或者说，分解算法之所以“困难”，是因为它们无法高效地扩展到大数。 - Greenstick

Answer 3

在大O符号中，n代表输入的大小，而不是输入本身（就像您的情况一样）。输入的大小是lg（n）位。因此，基本上您的算法是指数级别的。

- BiGYaN