Решите рекуррентное соотношение по теореме Мастера?

Question

Может кто-то просить прояснить это решение немного больше?

Т (п) = 2T (п^1/2) + войти п

Решение:

Пусть к = лог п,

Т (п) = Т (2^к) = 2T (2^(к/2)) + к

Подставляя в это уравнение S (к) = Т (2^к)

мы получаем, что

S (K) = 2S (к/2) + к

Теперь, это рекуррентное уравнение позволяет использовать основную теорему, которая указывает, что

S (K) = О (к лог к). Подставляя назад для T (n), следует, что T (n) - O (log n log log n)

Answer 1

Сколько раз вы можете продолжать разделять n на 2? Log_2 (n) раз. Поскольку Log_2 (n) - это то, что вам нужно, чтобы поднять 2, чтобы получить n.

Также loglog (n) - сколько раз вы можете взять квадратный корень из n, поэтому, возможно, эта замена не нужна, если вы это знаете.