Временная сложность этой степенной функции

#go #big-o

#Вперед #большой-о

Вопрос:

У меня есть этот код для вычисления мощности определенного числа

 func power(x, n int) int {
    if n == 0 {
        return 1
    }

    if n == 1 {
        return x
    }

    if n%2 == 0 {
        return power(x, n/2) * power(x, n/2)
    } else {
        return power(x, n/2) * power(x, n/2) * x
    }
}

игровая площадка go:

Итак, общее количество выполнений равно 1 2 4 … 2^ к

и в соответствии с формулой геометрической прогрессии

a(1-r ^ n) / (1-r)

сумма времени выполнения будет равна 2 ^ k, где k — высота двоичного дерева

Следовательно, временная сложность равна 2 ^ logn

Я прав? Спасибо 🙂

1. По-видимому, ваша формула для суммирования геометрических рядов неверна (когда r> 1). Коэффициент должен быть (r ^ n — 1) и (r — 1) [ни (1 — r ^ n), ни (1 — r)].

2. @ShudiptaSharma о, но я ссылался на эту формулу из вики: en.wikipedia.org/wiki/Geometric_progression

Ответ №1:

ДА.

Другой способ мышления о сложности рекурсивных функций — (количество вызовов) ** (высота рекурсивного дерева)

При каждом вызове вы выполняете два вызова, которые делят n на два, поэтому высота дерева равна logn, поэтому временная сложность равна 2 ** (logn), что равно O (n)

Смотрите Здесь Гораздо более формальное доказательство:

https://cs.stackexchange.com/questions/69539/time-complexity-of-recursive-power-code

1. Если вы присмотритесь, то обнаружите, что fn не выполняет 2 вызова одновременно. Каждый раз, когда он проходит через блок if-else. Это означает либо n%2 == 0, либо n%2 == 1, а не оба. Правильно. Таким образом, вы не можете просто рассматривать это как 2 дочерних вызова.

2. @ShudiptaSharma Но если вы посмотрите еще внимательнее, в обоих случаях есть два вызова: return power(x, n/2) * power(x, n/2) или return power(x, n/2) * power(x, n/2) * x

3. О, да, я это признаю. Я не заметил, что это происходит дважды с использованием оператора *. Приношу извинения за мои действия и восстанавливаю вашу репутацию.

Ответ №2:

Каждый раз, когда вы делите n на 2, если n <= 1. Итак, подумайте, сколько раз вы можете уменьшить n до 1 только путем деления на 0? Давайте посмотрим,

n = 26 n1 = 13 n2 = 6 (возьмите этаж 13/2) n3 = 3 n4 = 1 (возьмите этаж 3/2)

Допустим, x_th степень 2 больше или равна x. Затем,

 2^x >= n
or, log2(2^x) = log2(n)
or, x = log2(n)

Именно так вы находите временную сложность вашего алгоритма как log2 (n).

1. Нет, вы просто приняли во внимание количество вызовов, пока n не станет 1, что действительно равно log2 (n) . Но вам также необходимо учитывать количество вызовов в каждом вызове, которое равно 2, поэтому временная сложность равна O (n)