Временная сложность рекурсивной функции факторизации внутри цикла for - PullRequest
Новая
       6

Временная сложность рекурсивной функции факторизации внутри цикла for

0 голосов
/ 03 июля 2019

Вот мой алгоритм в псевдокоде: он возвращает список простых чисел, который дает факторизацию числа n. Например, 75 = 3 * 5 * 5 

public static ArrayList<Integer> FACTORISATION(int n) {
    if (PRIME(n)) {
        // return a one-element array
        return new ArrayList<Integer>(Arrays.asList(n));
    } else {
        // find a prime divisor, p
        for (int i = 2; i < Math.sqrt(n); i++) {
            if (n % i == 0) {
                ArrayList<Integer> newList = new ArrayList<>();
                newList.add(i);
                newList.addAll(FACTORISATION(n/i));
                return newList;
            }
        }
    }
    return new ArrayList<>();
}

По моему мнению, сложность времени можно рассчитать как: - 

T(n) = 2 + T(n-1/p) + T(n-2/p) +...
T(n) = nT(n-1/p)
T(n) = O(n!)

Метод PRIME(n) имеет сложность O(n)

Это правильно?

1 Ответ

0 голосов
/ 03 июля 2019

Это немного сложнее.Во-первых, пожалуйста, исправьте ошибку в вашем коде, она должна быть i <= Math.sqrt(n); вместо i < Math.sqrt(n);.

Давайте начнем с уникального представления целого числа как произведения степеней его простых делителей:

n = p 1 a 1 p 2 a 2 p 3 a 3 ... p k a k

(например, 120 = 2 3 3 1 5 1 ).Сколько раз цикл for в вашем коде будет выполняться для ввода n (не считая рекурсивных под-вызовов)?Точно i-1 раз, где i - наименьший простой делитель n.Это потому, что когда первый такой i найден, цикл завершается (оператор return newList;).Если n само по себе является простым, цикл for вообще не будет выполнен, потому что if (PRIME(n)) вернет true.

Для каких входных аргументов будет FACTORISATION(int n) вызываться (рекурсивно)?Обратите внимание, это будет называться для n, а затем для

н / п 1 ,

н / п 1 2,

..

н / п 1 a 1 ,

n/ p 1 a 1 p 2 ,

n / p 1 a 1 p 2 2 ,

..

n / p 1 a 1 p 2 a 2 ,

..

н / п 1 a 1 p 2 a 2 p 3 a 3 ... p k ,

..

н / п 1 a 1 p 2 a 2 p 3 a 3 ... p k a k -1 .

Тобыла самая сложная часть - если вы поняли это, все готово :) Теперь просто подытожьте время выполнения теста PRIME(n) и время выполненияот выполнения for цикла.Последний вносит общий вклад с (p 1 - 1) a 1 + (p 2 - 1) a 2 + ..+ (p k - 1) a k , в то время как первая часть добавляет n + n / p 1 + n / p 1 2 + ... + н / п 1 a 1 p 2 a 2 p 3 a 3 ... p k a k -1 .Невозможно оценить асимптотическую сложность этой суммы, не углубляясь в теорию чисел, но она намного лучше, чем O(n!) (для верхней оценки суммы делителей см., Например, здесь ).

...