Решение повторяемости T (n) = 2T (n/2) + Θ (1) подстановкой

Так что я почти уверен, что это O (n) (но может быть и нет?), Но как вы решаете это с заменой?

Если вы предполагаете, что T (n) ‹ = c * n, каковы шаги индукции?


recurrence math big-o
person evenodd    schedule 15.09.2014    source источник
comment
Расскажите нам, почему вы думаете, что это O (n)   -  person Matthew Herbst    schedule 16.09.2014
comment
На самом деле, может быть, он должен быть больше? Потому что, если вы замените O(n), вы получите T(n) ‹= cn + d. И d должен быть положительным, потому что этого не может быть. Может быть, это n ^ 2   -  person evenodd    schedule 16.09.2014
comment
Этот вопрос кажется не по теме, потому что он не о программировании. См. раздел О каких темах я могу задать здесь в Справочном центре. Возможно, лучше спросить на сайте Computer Science Stack Exchange.   -  person jww    schedule 16.09.2014
comment
Попробуйте решить две более простые задачи: T(n) = 2 * T(n/2) и T(n) = T(n/2) + O(1). Какая из этих проблем больше всего похожа на вашу? Можете ли вы применить результаты к вашей проблеме?   -  person dlev    schedule 16.09.2014

Ответы (3)


arrow_upward
10
arrow_downward

Прежде всего, я хотел бы ясно предположить, что Θ(1)=k, некоторая константа.

Далее, действуя методом подстановки, получаем

 T(n)=2T(n/2)+Θ(1)
     =2T(n/2)+k
     =2{2T(n/4)+k)+k
     =4T(n/4)+3k
     =...
     =n.T(1)+(n-1)k
     =n.k+(n-1)k
     =2nk-k
     =O(n).

Если вы предполагаете, что оно равно T(n) <= c * n, вы должны начать с T(1) и предположить, что T(n) верно, а затем продолжить показывать, что оно верно для T(n+1), используя предположение для T(n ).

Кстати, ваше предположение было верным!

person Am_I_Helpful    schedule 16.09.2014
comment
После 5-й строки обобщение должно быть 2^m T(n/2^m) + (2^m - 1)k. Теперь, чтобы сделать T(1), мы задаем 2^m = n, что дает нам 6-ю строку. - person Muntashir Akon; 11.11.2018

arrow_upward
1
arrow_downward

Для простоты предположим, что член O(1) скрывает некоторую константу c, так что рекуррентность действительно

T(n) = 2T(n/2) + c

Предположим также для простоты, что T(1) = c.

Вы рискуете (правильно) предположить, что

T(n) <= an + b

Для некоторых констант a и b. Попробуем доказать это индуктивно.

Для n = 1 нам нужно, чтобы a и b были такими, что

c <= a + b

Для индукционного шага мы хотим

T(n) <= 2T(n/2) + c

Подстановка нашего предположения дает

T(n) <= 2(an / 2 + b) + c

= an + 2b + c

Обратите внимание, что если 2b + c = b, то левая часть этого выражения будет an + b — нужная нам верхняя граница. Таким образом, нам нужно выбрать a и b так, чтобы

c <= a + b

2b + c = c

Один из возможных вариантов, который работает здесь, - это a = 2c и b = -c, что дает T (n) ‹ = 2cn - c = O (n).

Надеюсь это поможет!

person templatetypedef    schedule 16.09.2014

arrow_upward
0
arrow_downward

теорема Мастера хорошо подходит для этой задачи:

Сравнение данного уравнения

T(n) = 2T(n/2) + c

с формулами

T(n) = aT(n / b) + (nk logpn)
где a ›= 1, b › 1, k ›= 0 и p действительно

можно сказать, что он удовлетворяет условию a › bk, поскольку a = 2, b = 2 и k = 0,
итак, T(n) = θ(nlog б а) = θ(n)

person Bikash Pandey    schedule 25.10.2020