Может ли кто-то помочь решить эту рецидивирующую связь?

Ответ 1

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

Затем выясните, сколько раз вы повторяетесь (то есть высота дерева рекурсии). n - ваш размер проблемы, поэтому сколько раз мы можем разделить 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. Отбрасываем члены и константы нижнего порядка, поэтому θ (n).

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

Ответ 2

Используйте Master Theorem для решения таких рекуррентных отношений.

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

• T (n) = a T (n/b) + n ^c.. если n > 1

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

то для n степень b,

• если log _b a < c, T (n) = Θ (n ^c),
• если log _b a = c, T (n) = Θ (n ^c log n),
• если log _b a > c, T (n) = Θ (n ^{log _b a}).

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

В этом случае

a = b = 2;
 log _b a = 1; c = 0 (так как n ^c= 1 = > c = 0)

Так применим случай (3). Итак T(n) = Θ(n):)

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

Пусть m = log ₂ n;

= > T (2 ^m) = T (2 ^m/2) + 0(1)

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

Применить случай (2).

Ответ 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).

Ответ 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.

Ответ 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, где log находится в базе 2. Очевидно, что это O (log (log (n)) отношение.

Ответ 6

В большинстве случаев лучший способ справиться с повторением - это рисовать дерево повторения и тщательно обрабатывать базовый случай.

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

В повторении сначала попробуйте подставить n = 2^k При повторной второй попытке подстановка n = 2^2^k