Warum gibt es die Regelmäßigkeitsbedingung im Hauptsatz?

15

Ich habe die Einführung in Algorithmen von Cormen et al. und ich lese die Aussage des Hauptsatzes ab Seite 73 . In Fall 3 gibt es auch eine Regelmäßigkeitsbedingung, die erfüllt sein muss, um den Satz zu verwenden:

... 3. Wenn

f(n)=Ω(nlogba+ε)

für eine konstante und wennε>0

af(n/b)cf(n)      [ dies ist die Regelmäßigkeitsbedingung ]

für eine Konstante und für alle ausreichend großen dann ..c<1n

Kann mir jemand sagen, warum die Regelmäßigkeitsbedingung benötigt wird? Wie versagt der Satz, wenn die Bedingung nicht erfüllt ist?

Raphael
quelle
Kannst du schreiben, was der Fall ist und was die regulatorische Bedingung ist?
3
Ich habe keine definitive Antwort für Sie, aber wenn die Regelmäßigkeitsbedingung nicht zutrifft, nehmen die Teilprobleme immer mehr Zeit in Anspruch, je kleiner sie sind, sodass Sie eine unendliche Komplexität erhalten.
Ich bin nicht sicher, ob die Regelmäßigkeitsbedingung für den Abschluss des Theorems erfüllt sein muss, aber ich denke, dass sie für den verwendeten Beweis erforderlich ist. Mit der Regelmäßigkeitsbedingung haben Sie einen ziemlich einfachen Beweis, ohne den es zumindest haarig wäre.

Antworten:

10

Kein strenger Beweis, sondern eine Erklärung aus der Vogelperspektive.

Stellen Sie sich die Wiederholung als Baum vor. Der dritte Fall deckt das Szenario ab, in dem der Wurzelknoten die Laufzeit asymptotisch dominiert, dh der größte Teil der Arbeit wird im Messknoten über dem Wiederholungsbaum ausgeführt. Dann ist die Laufzeit .Θ ( f ( n ) )aT(n/b)+f(n)Θ(f(n))

Um sicherzustellen, dass der Root tatsächlich mehr Arbeit leistet, benötigen Sie die

af(n/b)cf(n) .

Dies besagt, dass (die Menge der in der Wurzel geleisteten Arbeit) mindestens so groß sein muss wie die Summe der in den unteren Ebenen geleisteten Arbeit. (Die Wiederholung wird mal auf der Eingabe aufgerufen .)a n / bf(n)an/b

ZB für die Wiederholung die Arbeit auf der Ebene unter der Wurzel ein Viertel so groß und wird nur zweimal gegen so dass die Wurzel dominiert.( n / 4 + n / 4 ) nT(n)=2T(n/4)+n(n/4+n/4)n

Was aber, wenn die Funktion die Regelmäßigkeitsbedingung nicht erfüllt? ZB statt ? Dann ist die Arbeit in den unteren Ebenen möglicherweise größer als die in der Wurzel, sodass Sie nicht sicher sind, ob die Wurzel dominiert.ncos(n)n

Die unfun Katze
quelle
3
Ich habe eine schönere Formatierung für Ihren Mathe-Text verwendet. Sie können auf den Link "bearbeitet" klicken und sehen, was ich getan habe.
Juho
7

Sei und , so dass Für den Fall 3 benötigen wir (für einige ) und die Regelmäßigkeitsbedingung (für etwas ). Die Regelmäßigkeitsbedingung erhält man aus dem Beweis, dh es handelt sich um ein beweiserzeugtes Konzept. Obwohl die Regelmäßigkeitsbedingung nicht erforderlich ist (siehe das Beispiel in Wikipedia, ), können Sie sie nicht vollständig löschen, wie das folgende Beispiel zeigt. Betrachte Seia=1b=2

T(2n)=k=0nf(2k).
f(n)=Ω(nϵ)ϵ>0f(n/2)(1δ)f(n)δ>0f(n)=n(2cosn)
f(2n)=22log2n>22log2n1=2n/2.
n=2m+11. Dann ist Es ist also nicht wahr, dass .T ( 2 n ) = Θ ( f ( 2 n ) )
T(2n)=k=0mt=2k2k+1122k=k=0m22k+k=Θ(22m+m),f(2n)=22m.
T(2n)=Θ(f(2n))

Es gibt einen allgemeineren Satz, Akra-Bazzi, in dem die Regelmäßigkeitsbedingung durch eine explizite Größe ersetzt wird, die in das Ergebnis eingeht.

Yuval Filmus
quelle
Entschuldigen Sie, dass Sie diese alte Antwort wieder aufgenommen haben. Können Sie erklären, warum Ihre Funktion f die Regelmäßigkeitsbedingung verletzt?
Maiaux
Manchmal ist . f(n/2)=f(n)
Yuval Filmus