Какова временная сложность нахождения максимума рекурсивно

Question

Я просто хотел убедиться, что я иду в правильном направлении. Я хочу найти максимальное значение массива путем его рекурсивного разбиения и найти максимальное значение для каждого отдельного массива. Поскольку я делю это, это будет 2 * T (n / 2). И поскольку я должен сделать сравнение в конце для двух массивов, у меня есть T (1). Итак, будет ли мое отношение повторения таким:

T = {2 * T (n / 2) + 1, когда n> = 2; T (1), когда n = 1;

и, следовательно, моя сложность будет тета (nlgn)?

Answer 1

Формула, которую вы составили, кажется правильной, но ваш анализ не идеален.

T = 2*T(n/2) + 1 = 2*(2*T(n/4) + 1) + 1 = ...

Для i-й итерации вы получите:

Ti(n) = 2^i*T(n/2^i) + i

что теперьВы хотите знать, для чего я делаю n / 2 ^ я равен 1 (или почти любой константе, если хотите), чтобы вы достигли конечного условия n = 1.Это было бы решением n / 2 ^ I = 1 -> I = Log2 (n).Установите его в уравнении для Ti, и вы получите:

TI(n) = 2^log2(n)*T(n/2^log2(n)) + log2(n) = n*1+log2(n) = n + log2(n)

, и вы получите T (n) = O (n + log2 (n) (как сказал @bdares) = O (n) (простокак сказал @bdares)

Answer 2

Нет, нет ... вы тратите O (1) время на каждую рекурсию.

Сколько их?

Есть N листьев, так что вы знаете, что это по крайней мере O(Н).

Сколько вам нужно сравнить, чтобы найти абсолютный максимум?Это O (log (N)).

Сложите их вместе, не умножайте.O (N + log (N)) - сложность вашего времени.