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

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

这种现象称为伪多项式:这种复杂性似乎是多项式的,但实际上并非如此.如果您询问某个复杂度(此处为n)是否为多项式,则必须考虑复杂性与输入大小的关系.在大多数情况下,例如排序(例如合并排序可以在O(n lg n)中求解),n描述输入的大小(元素的数量).但是,在这种情况下,n没有描述输入的大小; 它是输入值.那么,n的大小是多少？一个自然的选择是n中的位数,大约为lg n.因此,让W = LGñ是大小ñ.现在我们看到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位)).