Когда на самом деле можно применить основную теорему?

Я очень расстроен по этому поводу.

В 3-м издании CLRS, стр. 95 (глава 4.5), упоминается, что такие повторения, как

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

не может быть решена с помощью основной теоремы, потому что разница

f(n)/n^(log_b(a)) = (n lg n)/n^1 = lg n

не является полиномиальным.

Но затем я наткнулся на такие страницы, как это, где, в В нижней части страницы упоминается точно такое же повторение и говорится, что его МОЖЕТ решить с помощью Главной теоремы, потому что он попадает в «расширенный случай 2», даже если разница неполиномиальна. Он становится n lg^2 n (увеличивая коэффициент журнала на f(n) на единицу).

Затем я наткнулся на такие страницы, как эта, где в примере (e) кажется как явное применение расширенного случая 2 (повторяемость T(n) = 4T(n/2) + n^2 lg n), но тогда решение не n^2 log^2 n, а скорее n^2 log n! Я ошибаюсь или бумага не та?

Может ли кто-нибудь прояснить противоречия и прояснить, когда именно можно использовать Основную теорему, а когда нельзя? Когда проверка полиномиальной разности имеет значение, а когда нет? Можно ли использовать расширенный случай 2 или он действительно что-то нарушает?

РЕДАКТИРОВАТЬ:

Я попытался решить повторение (e) непосредственно из второй статьи и получил:

T(n) = n^2 lg^2(n)/2 + n^2 lg(n)/2

Разве это не большая тета n^2 lg^2 n?


algorithm polynomials big-o master-theorem asymptotic-complexity
person AJJ    schedule 03.01.2016    source источник
comment
Обратите внимание, что случай 2 Основной теоремы в книге отличается от обобщенной формы, с которой вы сталкиваетесь в другом месте (включая ваши примеры). Откуда взялась обобщенная форма? Упражнение 4.6-2 в книге, на самом деле довольно легко доказать это самостоятельно. :-)   -  person Michael Foukarakis    schedule 03.01.2016
comment
@MichaelFoukarakis Не могли бы вы сказать, что правило полиномиальной разности применяется только к случаям 1 и 3?   -  person AJJ    schedule 03.01.2016
comment
Правило полиномиальной разности является более строгим утверждением, чем полилогарифмический случай. Это относится ко всем 3 случаям. В случае № 2 просто позволено расслабиться.   -  person Michael Foukarakis    schedule 03.01.2016

Ответы (1)


arrow_upward
3
arrow_downward

В книге говорится, что ее нельзя решить с помощью Case 3:

даже если кажется, что он имеет правильную форму: ... Вы можете ошибочно подумать, что должен применяться случай 3

Однако эту рекуррентную формулу можно решить с помощью основной теоремы, случай 2.

T(n) = 2T(n/2) + nlgn:

Мы определяем:

a = 2, b = 2, f(n) = nlgn

Используя случай 2 основной теоремы:

c = log_2(2) = 1
k = 1

И f(n) действительно находится в Theta(nlogn).

Таким образом, все условия для овладения теоремой, случай 2 применимы, и мы можем сделать вывод:

T(n) is in Theta(n^c * log(n)^(k+1)) = Theta(n*log(n)^2)

Короче говоря, основная теорема имеет 3 случая. В каждом случае есть свои предпосылки для применения. Случай 3 имеет более сложные предпосылки, поскольку он также требует сходимости.
Поскольку предварительные условия для случая 3 не применяются к этой формуле, вы не можете использовать вариант 3. Однако предварительные условия для случая 2 применяются, и вы можете их использовать.

person amit    schedule 03.01.2016
comment
В нем упоминается, что случай 3 неприменим, но за несколько строк до этого говорится, что основная теорема в целом к ​​нему неприменима (основной метод не применяется к повторению...), а затем вскоре после этого говорится, что вы может ошибочно подумать, что должен применяться случай 3... На странице 96 утверждается, что повторение попадает в промежуток между случаями 2 и случаями 3. Книга неверна? - person AJJ; 03.01.2016
comment
Как насчет этого: согласны ли вы со следующими утверждениями: CLRS неверна, случай 2 основной теоремы применим к T(n) = 2T(n/2) + n lg n и имеет большую Theta n lg^2 n, вторая статья, на которую я ссылаюсь, неверна, и T(n) = 4T(n/2) + n^2 lg n также является случаем 2, поэтому большая Theta n^2 lg^2 n, и концепция полиномиальной разности применяется только при работе со случаями 1 и 3? - person AJJ; 03.01.2016
comment
(1) CLRS не определяет, что это не случай 2, он фактически указывает вам на доказательство случая 2 как на решение этой проблемы. Однако я согласен, что формулировка в книге несколько вводит в заблуждение. (2) Полиномиальная разность требуется только в случае 3, а в случаях 1 и 2 - нет. - person amit; 03.01.2016
comment
Где в книге он указывает на случай 2 как на решение проблемы? У вас есть другая версия CLRS, где это упоминается? В моей книге повторение называется неразрешимым с помощью Главной теоремы, и случай 3 используется как пример того, что вы могли бы попробовать, но это было бы неверно из-за правила полиномиальной разности. В нем не упоминается и даже не намекается, что вместо этого применяется случай 2. Он прямо утверждает, что неразрешим с помощью Главной теоремы (с чем я не согласен). - person AJJ; 03.01.2016
comment
Там написано (See Exercise 4.6-2 for a solution.). и это упражнение является доказательством случая 3... (3-е издание) - person amit; 03.01.2016
comment
Вы правы, и упражнение 4.6.-2 действительно предполагает применение расширенного случая 2. Я думаю, что формулировка на странице 95 вводит в заблуждение, но вы правы. А как насчет вашей точки зрения о полиномиальной разности? См. нижнюю часть страницы 94 и верхнюю часть страницы 95: в первом случае не только f (n) должно быть меньше, чем n ^ (log_b (a)), но и полиномиально меньше [...] в третьем случае , должно быть не только f(n) больше, чем n^(log_b(a)), оно также должно быть полиномиально больше... Разве это не предполагает, что правило полиномиальной разности применимо к случаям 1 и 3 одинаково? - person AJJ; 03.01.2016
comment
(обратите внимание, что я не ссылаюсь на правило только для случая 3 об условии регулярности, которое является отдельным условием) - person AJJ; 03.01.2016
comment
@ArukaJ Хорошо, я вижу твое замешательство. Да, для случаев 1+3 требуется полиномиальная разность (отсюда и использование O(n^(x-eps))/Omega(n^(x+eps)). В случае 2 это не требуется. - person amit; 03.01.2016
comment
И да, T(n)=4T(n/2) + n^2lgn действительно находится в Theta(n^2 log(n)^2) с таким же корпусом. - person amit; 03.01.2016