Почему в основной теореме есть условие регулярности?

15

Я читал Введение в алгоритмы от Cormen et al. и я читаю формулировку основной теоремы, начиная со страницы 73 . В случае 3 также существует условие регулярности, которое необходимо выполнить, чтобы использовать теорему:

... 3. Если

е(N)знак равноΩ(Nжурналбa+ε)

для некоторой константы и еслиε>0

aе(N/б)се(N)      [ это условие регулярности ]

для некоторой константы и для всех достаточно больших , тогда ..нс<1N

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

Рафаэль
источник
Вы можете написать, в чем дело и каково нормативное условие?
3
У меня нет однозначного ответа для вас, но кажется, что если условие регулярности не выполняется, тогда подзадачи занимают все больше и больше времени, чем они меньше, так что вы получаете бесконечную сложность.
Я не уверен, что условие регулярности необходимо для выполнения заключения теоремы, но я думаю, что оно необходимо для использованного доказательства. С условием регулярности у вас есть довольно прямое доказательство, без которого, по крайней мере, оно будет волосатым.

Ответы:

10

Не строгое доказательство, а объяснение «от макушки головы».

Вообразите повторение как дерево. Третий случай охватывает сценарий, когда корневой узел асимптотически доминирует во время выполнения, то есть большая часть работы выполняется в ничтожном узле на вершине дерева повторений. Тогда время запуска является Θ ( F ( п ) ) .aT(N/б)+е(N)Θ(е(N))

Чтобы убедиться, что рут действительно делает больше, вам нужно

.aе(N/б)се(N)

Это говорит о том, что (объем работы, выполненной в корне) должен быть по меньшей мере таким же большим, как сумма работы, выполненной на более низких уровнях. (Повторение называется раз на п / б входа.)е(N)aN/б

Например, для повторения работа на уровне ниже корня на одну четвертую больше и выполняется только дважды ( n / 4 + n / 4 ) по сравнению с n, поэтому корень доминирует ,T(N)знак равно2T(N/4)+N(N/4+N/4)N

Но что, если функция не удовлетворяет условию регулярности? Например, вместо n ? Тогда работа, выполняемая на более низких уровнях, может быть больше, чем работа, выполняемая в корне, поэтому вы не уверены, что корень доминирует.соз(N)N

Несчастный кот
источник
3
Я использовал более хорошее форматирование для вашего математического текста. Вы можете нажать на ссылку «отредактировано» и посмотреть, что я сделал.
Юхо
7

Пусть и b = 2 , так что T ( 2 n ) = n k = 0 f ( 2 k ) . Чтобы применить случай 3, нам нужно f ( n ) = Ω ( n ϵ ) (для некоторых ϵ > 0 ) и условие регулярности f ( n / 2 ) ( 1 - δ ) faзнак равно1бзнак равно2

T(2N)знак равноΣКзнак равно0Nе(2К),
е(N)знак равноΩ(Nε)ε>0 (для некоторого δ > 0 ). Вы получаете условие регулярности из доказательства, т.е. это сгенерированное доказательством понятие. Хотя условие регулярности не является обязательным (рассмотрим пример, приведенный в Википедии, f ( n ) = n ( 2 - cos n ) ), вы не можете полностью его отбросить, как показано в следующем примере. Рассмотрим f ( 2 n ) = 2 2 log 2 n > 2 2 log 2 n -е(N/2)(1-δ)е(N)δ>0е(N)знак равноN(2-созN) Пустьn=2m+1-1. Тогда T(2n)= m k = 0 2 k + 1 - 1 t = 2 k 2 2 k = m k = 0 2 2 k +k=Θ(2 2 m +
е(2N)знак равно22журнал2N>22журнал2N-1знак равно2N/2,
Nзнак равно2м+1-1 Поэтому неверно, что T ( 2 n ) = Θ ( f ( 2 n ) ) .
T(2N)знак равноΣКзнак равно0мΣTзнак равно2К2К+1-122Кзнак равноΣКзнак равно0м22К+Кзнак равноΘ(22м+м),е(2N)знак равно22м,
T(2N)знак равноΘ(е(2N))

Существует более общая теорема Акра-Бацци, в которой условие регулярности заменяется явной величиной, которая входит в результат.

Юваль Фильмус
источник
Извините за возобновление этого старого ответа. Не могли бы вы уточнить, почему ваша функция f нарушает условие регулярности?
Майо
е(N/2)знак равное(N)