Определение сложности алгоритма целочисленной факторизации

Я начинаю изучать вычислительную сложность, нотацию 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)

Что я считаю неправильным, потому что алгоритмы факторизации должны быть сложными в вычислительном отношении, они даже не могут быть полиномиальными. Так что вы предлагаете мне помочь? Может быть, я слишком устал в это время ночи, и я все лажаю: (

Заранее благодарю.

12
задан Ricardo Ferreira 15 May 2011 в 01:19
поделиться