Может кто-нибудь помочь решить это рецидивовое отношение? [закрыто

Question

T(n) = 2T(n/2) + 0(1)

T(n) = T(sqrt(n)) + 0(1)

В первом я использую метод замещения для N, logn и т. Д.; Все дало мне неправильные ответы.
Рецитарные деревья: я не знаю, могу ли я подать заявку, так как root будет постоянным.

Может ли кто-нибудь помочь?

Answer 1

Давайте посмотрим на первый. Прежде всего, вам нужно знать t (базовый случай). Вы упомянули, что это постоянное, но когда вы делаете проблему, важно, чтобы вы записали его. Обычно это что-то вроде t (1) = 1. Я буду использовать это, но вы можете обобщить на все возможное.

Далее узнайте, сколько раз вы повторите (то есть высота дерева рекурсии). n Размер вашей проблемы, так сколько раз мы можем многократно разделить на 2? Математически говоря, что я, когда n/(2^i) = 1? Установите это, держите его на него позже.

Далее сделайте несколько замений, пока не начните заметить шаблон.

T(n) = 2(2(2T(n/2*2*2) + θ(1)) + θ(1)) + θ(1)

ОК, шаблон состоит в том, что мы умножаем T () на 2 куча раз, и разделите N на 2 куча раз. Сколько раз? i раз.

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

Для терминов Big-θ в конце мы используем милый трюк. Посмотрите выше, где у нас есть несколько замеек, и игнорируйте часть T (). Мы хотим сумму терминов θ. Обратите внимание, что они добавляют до (1 + 2 + 4 + ... + 2^i) * θ(1). Отказ Можете ли вы найти закрытую форму для 1 + 2 + 4 + ... + 2^i? Я дам тебе это; это (2^i - 1). Отказ Это хороший, чтобы просто запомнить, но Вот как вы подумаете это.

В любом случае, все во всем, что мы получаем

T(n) = (2^i) * T(n/(2^i)) + (2^i - 1) * θ(1)

Если вы решаете для i раньше, тогда вы знаете, что i = log_2(n). Отказ Подключите это, сделайте некоторую алгебру, и вы спускаетесь к

T(n) = n*T(1) + (n - 1)*θ(1). T(1) = 1. Отказ Так T(n) = n + (n - 1)*θ(1). Отказ Который N раз постоянно, плюс постоянная, плюс н. Мы бросаем условия и постоянные более низкого порядка, так что это θ (n).

Prasoon Saurav справа от использования главного метода, но важно, чтобы вы знали, что говорит о рецидиве. Что спрашивать, сколько работы я делаю на каждом шаге, и какое количество шагов для ввода размера n?

Answer 2

Использовать Master Theorem решить такие рецидива отношения.

Позволять а. быть целым числом, больше или равно 1 и преступность быть настоящим числом, превышающим 1. Пусть слияние быть положительным действительным числом и подразделение неотрицательное реальное число. Учитывая рецидив формы

• T (n) = a t (n / b) + n^{слияние} .. если n> 1

• T (n) = d .. если n = 1

Тогда для Na Power of B,

1. Если логи_{преступность} a <c, t (n) = θ (n^{слияние}),
2. Если логи_{преступность} a = c, t (n) = θ (n^{слияние} log n),
3. Если логи_{преступность} A> C, T (N) = θ (n^{журнал_{преступность} а.}).

1) T(n) = 2T(n/2) + 0(1)

В этом случае

A = B = 2;
журнал_{преступность} A = 1; C = 0 (так как n^{слияние} = 1 => c = 0)

Так что дело (3) применимо. Так T(n) = Θ(n) :)

---

2) T(n) = T(sqrt(n)) + 0(1)

Пусть m = log₂ n;

=> T (2^М.) = T (2^{м / 2.} ) + 0(1)

Теперь переименование K (M) = T (2^М.) => K (m) = k (м / 2) + 0(1)

Применить чехол (2).

---

Answer 3

Для части 1 вы можете использовать основную теорему, так как предлагается @Prasoon Saurav.

Для части 2 просто расширяйте рецидив:

T(n) = T(n ^ 1/2) + O(1)         // sqrt(n) = n ^ 1/2
     = T(n ^ 1/4) + O(1) + O(1)  // sqrt(sqrt(n)) = n ^ 1/4
     etc.

Серия будет продолжать k Условия до n ^ 1/(2^k) <= 1, т.е. 2^k = log n или k = log log n. Отказ Это дает T(n) = k * O(1) = O(log log n).

Answer 4

Давайте посмотрим на первое повторение, T (N) = 2T (N / 2) + 1. N / 2 - наш ключ здесь: Параметр каждого вложенного срока половина его родителя. Поэтому, если мы начнем с n = 2 ^ k, то у нас будет K терминов в нашем расширении, каждое добавление 1 к общей сложности, прежде чем мы ударим наш базовый случай, T (0). Следовательно, предполагая t (0) = 1, можно сказать t (2 ^ k) = k + 1. Теперь, поскольку n = 2 ^ k, мы должны иметь k = log_2 (n). Следовательно, t (n) = log_2 (n) + 1.

Мы можем применить тот же трюк для вашего второго рецидива, T (n) = t (n ^ 0,5) + 1. Если мы начнем с n = 2 ^ 2 ^ k, у нас будет K термины в нашем расширении, каждое добавление 1 к Всего. Предполагая, что t (0) = 1, мы должны иметь t (2 ^ 2 ^ k) = k + 1. Так как n = 2 ^ 2 ^ k, мы должны иметь k = log_2 (log_2 (n)), следовательно, t (n) = log_2 (log_2 (n)) + 1.

Answer 5

Рецидивные отношения и рекурсивные функции также должны быть решены, начиная с F (1). В случае 1, T (1) = 1; T (2) = 3; T (4) = 7; T (8) = 15; Понятно, что t (n) = 2 * n -1, который в o обозначении o (n).
Во втором случае t (1) = 1; T (2) = 2; T (4) = 3; T (16) = 4; T (256) = 5; T (256 * 256) = 6; Это займет мало времени, чтобы узнать, что t (n) = log (log (n)) + 1, где журнал находится в базе 2. Очевидно, что это O (log (log (n)) отношение.

Answer 6

Большую часть времени лучший способ справиться с рецидивом - нарисовать рецидивовое дерево и осторожно обрабатывать базовый чехол.

Однако здесь я дам вам небольшой подсказку для решения метода замещения.

В рецидиве сначала попробуйте замена n = 2^kВ рецидиве второй попробуйте замена n = 2^2^k