Определение сложности алгоритма целочисленной факторизации - PullRequest
Новая
       83

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

12 голосов
/ 15 мая 2011

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

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

Заранее спасибо.

Ответы [ 3 ]

27 голосов
/ 15 мая 2011

Это явление называется псевдополиномиальность : сложность, которая кажется полиномиальной, но на самом деле это не так.Если вы спросите, является ли определенная сложность (здесь 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 бит)).

0 голосов
/ 15 мая 2011

В нотации big-O n - это размер ввода, а не сам ввод (как в вашем случае).Размер ввода составляет lg(n) бит.Так что в основном ваш алгоритм экспоненциальный.

0 голосов
/ 15 мая 2011

Используйте тот факт, что ваш алгоритм является рекурсивным.Если f (x) - это число операций, принимаемых за коэффициент, если n - первый найденный коэффициент, то f (x) = (n-1) + f (x / n).Наихудший случай для любого алгоритма факторинга - это простое число, сложность вашего алгоритма которого равна O (n).

Алгоритмы факторинга являются «сложными», главным образом потому, что они используются для неприлично больших чисел.

...