какова временная сложность этого метода, который проверяет, может ли число k быть представлено как n ^ p - PullRequest
Новая
       6

какова временная сложность этого метода, который проверяет, может ли число k быть представлено как n ^ p

6 голосов
/ 14 апреля 2020

Временная сложность нижеописанного метода? Я вычисляю это как log (n) * log (n) = log (n) 

public int isPower(int A) {
    if (A == 1) 
        return 1;

    for (int i = (int)Math.sqrt(A); i > 1; i--){
        int p = A;

        while (p % i == 0) {
            p = p / i;
        }

        if (p == 1) 
            return 1;
    }

    return 0;
}

Ответы [ 2 ]

4 голосов
/ 14 апреля 2020

Вы повторяете с sqrt(A) to 2. Тогда ты пытался факторизовать. Для простого числа ваш код повторяется sqrt (A) раз. в лучшем случае. если число равно 2 ^ 30, тогда ваш код выполняет sqrt (2 ^ 30) * 30 означает sqrt (n) * log (n) раз.

Итак, сложность вашего кода: sqrt(n) * log(n)

3 голосов
/ 14 апреля 2020

Сложность в худшем случае:

for(..) выполняется sqrt(A) раз

Тогда while(..) зависит от простой факторизации A=p_1^e1*p_2^e_2*..*p_n^e_n, поэтому Max(e_1,e_2,..,e_n) наихудший случай или примерно Max(log_p_1(A),log_p_2(A),..)

Максимум while(..) будет исполняться log(A) приблизительно раз.

, поэтому общая грубая сложность в худшем случае = sqrt(A)*log(A), исключая постоянные факторы

Наихудшая сложность возникает для чисел A, которые являются произведениями разных целых чисел ie A = n_1^e_1*n_2^e_2*..

Сложность в среднем случае:

Дано чисел, которые являются произведениями разных целых чисел более многочисленны, чем числа, которые являются просто степенями одного целого числа, в данном диапазоне, тогда выбор случайного числа, скорее всего, будет произведением различных целых чисел, ie A = n_1^e_1*n_2^e_2... Таким образом, сложность среднего случая примерно такая же, как сложность в худшем случае ie sqrt(A)*log(A)

сложность в лучшем случае:

сложность в лучшем случае возникает, когда число A действительно степень одного целого числа / простого числа ie A = n^e. Тогда алгоритм в этом случае занимает меньше времени. Я оставляю это как упражнение для вычисления сложности в лучшем случае.

PS. Другой способ убедиться в этом - понять, что, проверяя, является ли число степенью простого / целого числа, фактически нужно преобразовать число в его простое факторизацию (что и делается в этом алгоритме), что по сути сложность (см., например, сложность факторинга по пробному делению ).

SO должен иметь поддержку mathjax, поскольку cs.stackexchange имеет: p!

...