13

我开始研究计算复杂性、BigOh 表示法等，我的任务是做一个整数分解算法并确定它的复杂性。我已经编写了算法并且它正在工作，但是我在计算复杂度时遇到了麻烦。伪代码如下：

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)

我认为这是错误的，因为分解算法应该是计算困难的，它们甚至不能是多项式的。那么你有什么建议可以帮助我？也许我在晚上的这个时候太累了，我把这一切都搞砸了:(

先感谢您。

4

3 回答 3

28

这种现象被称为伪多项式：一种看似多项式的复杂性，但实际上不是。如果您询问某个复杂度（此处为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 位））。

于 2011-05-15T01:30:48.013 回答
0

使用您的算法是递归的事实。如果 f(x) 是要考虑的操作数，如果 n 是找到的第一个因数，则 f(x)=(n-1)+f(x/n)。任何因式分解算法的最坏情况是素数，算法的复杂度为 O(n)。

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

于 2011-05-15T02:33:05.847 回答
0

在大 O 表示法中，n是输入的大小，而不是输入本身（如您的情况）。输入的大小是lg(n)位。所以基本上你的算法是指数的。

于 2011-05-15T05:39:59.053 回答