algorithm - 确定整数分解算法的复杂性

Question

我开始研究计算复杂性、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)

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

提前谢谢你。

Answer 1

这种现象称为 pseudopolynomiality :看似多项式的复杂性，但实际上并非如此。如果您询问某个复杂度(此处为 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 位)。