Разделяй и властвуй, чтобы решить силу числа, анализ времени выполнения с основной теоремой - PullRequest
Новая
       42

Разделяй и властвуй, чтобы решить силу числа, анализ времени выполнения с основной теоремой

2 голосов
/ 02 июля 2019

Я реализовал алгоритм «разделяй и властвуй» для вычисления степени числа: 

public static void main(String[] args) {
    System.out.println("Result: " + pow(2, 1));
    System.out.println("Result: " + pow(2, 9));
    System.out.println("Result: " + pow(2, 8));
    System.out.println("Result: " + pow(2, 0));
}

private static int pow(int n, int pow) {
    if(pow == 0) {
        return 1;
    }

    if(pow > 2) {
        int leftPow;
        int rightPow;

        if(pow % 2 != 0) {
            leftPow = pow/2;
            rightPow = pow/2+1;
        } else {
            leftPow = pow/2;
            rightPow = leftPow;
        }

        return pow(n, leftPow) * pow(n, rightPow);
    } else {
        if(pow == 1) {
            return n;
        } else {
            return n * n;
        }
    }
}

Мой метод работает, так как вывод: 

Result: 2
Result: 512
Result: 256
Result: 1

Теперь я пытаюсьопределить время выполнения моего алгоритма, используя мастер-теорему:

Я предполагаю, что

так как рекурсивный вызов появляется два раза,

поскольку я создаю две подзадачи из одной проблемы

и, поскольку объединение результатов занимает постоянное время.

Постоянная водораздела () должно быть.

С этими значениями я предполагаю, что первое правило теоремы выполнено:, с, поскольку.

Поэтому время выполнения должно быть:.

Я совершенно не уверен в этом результате, так как у меня никогда не было случая,

Является ли мой анализ правильным?

1 Ответ

3 голосов
/ 02 июля 2019

Во-первых, вы должны заметить, что сложность будет объяснена на основе pow. Таким образом, n в вашем анализе означает pow, а не n переменную в вашей программе.

Во-вторых, поскольку число вычислений, таких как сравнение и умножение, является постоянным (менее 10 для вашей программы), то f(n) = \Theta(1), и вы можете написать его f(n) = 1 здесь.

Следовательно, сложность равна T(n) = 2T(n/2) + 1 (вы также можете увидеть метод Акра-Бацци) и T(n) = \Theta(n).

...