Wie analysiere ich einen randomisierten rekursiven Algorithmus?

8

Betrachten Sie den folgenden Algorithmus, wobei c eine feste Konstante ist.

void partition(A[1..m], B[1..n])
{
   if m=1 or n=1
      return

   k = random(min(c,m,n));
   partition A into k sublists Asub[1..k] at k-1 distinct random indices
   partition B into k sublists Bsub[1..k] at k-1 distinct random indices

   for i = 1 to k
     for j = 1 to k
        partition(Asub[i], Bsub[j])

   Do something that takes O(n+m) time.
}

Was ist die erwartete Laufzeit dieses Algorithmus? Die Laufzeit scheint O(mn) , aber ich kann den Beweis dafür nicht finden.

Wenn wir stattdessen die Eingabelisten in k verschiedene Teile gleicher Länge aufteilen würden, hätten wir die Wiederholung T(n,m)=k2T(n/k,m/k)+O(n+m) mit BasisfallT(1,n)=T(m,1)=O(1) ; es ist nicht schwer zu beweisen, dassT(n,m)=O(mn) . Der Algorithmus partitioniert die Eingabe jedoch in einen Zufall zufällige Anzahl von Teilen mitGrößen. (Wie üblich ist "zufällig" die Abkürzung für "gleichmäßig zufällig".) Wie analysiert man einen solchen Algorithmus?

Saeed
quelle
Ihr Algorithmus namens Partition ist vom Typ a Liste -> Liste -> nichtig, aber es scheint mir, dass es in Ihrem letzten Aufruf des Algorithmus Typ hata ->a -> nichtig? Verstehe ich etwas falsch? a
Gopi
8
Die Frage ist schlecht geschrieben, aber darunter befindet sich eine echte Frage zur Analyse randomisierter Rezidive.
Suresh Venkat
5
Hauptbearbeitung. Hoffentlich habe ich den Sinn der Frage bewahrt.
Jeffs
1
@ Jɛ ff E jetzt solltest du es beantworten :)
Suresh Venkat
1
Haben Sie sich das Chaudhuri-Dubhashi-Papier über probabilistische Rezidive angesehen (dies entwickelt Karps ursprüngliche Arbeit zu diesem Problem weiter): sciencedirect.com/science/article/pii/S0304397596002617
Suresh Venkat

Antworten:

9

Hier ist ein Beweis dafür, dass dieser Algorithmus in Zeit in Erwartung und mit hoher Wahrscheinlichkeit.O(nm)

Betrachten Sie zunächst den Algorithmus, der so modifiziert wurde, dass in { 2 , 3 , . . , min ( c , n ) } statt zufällig in { 1 , 2 , . . . , min ( c , n ) } .k{2,3,..,min(c,n)}{1,2,...,min(c,n)}

Lemma 1. Für diesen modifizierten Algorithmus ist die Zeit unabhängig von der zufälligen Auswahl des Algorithmus immer .O(nm)

Beweis. Fixieren Sie einen Eingang und B [ 1 .. m ] und fixieren Sie die zufälligen Auswahlmöglichkeiten des Algorithmus beliebig. Bei jedem (möglicherweise rekursiven) Aufruf von partition () entsprechen die beiden Argumente jeweils zwei Subarrays: einem Subarray A [ i 1 . . i 2 ] von A und einem Subarray B [ j 1 . . j 2 ] von B . Identifizieren Sie einen solchen Anruf mit dem Rechteck [ i 1A[1..n]B[1..m]A[i1..i2]AB[j1..j2]B . Somit ist der Aufruf der obersten Ebene [ 0 , n ] × [ 0 , m ] , und jeder rekursive Aufruf entspricht einem Unterrechteck innerhalb dieses n × m- Rechtecks. Diese Rechtecke bilden einen Baum, in dem das einem Anruf entsprechende Rechteck als Kinder die Rechtecke enthält, die den direkt von diesem Anruf getätigten Anrufen entsprechen. Jedes übergeordnete Rechteck wird durch seine untergeordneten Rechtecke unterteilt, die ein k × k bilden[i11,i2]×[j11,j2][0,n]×[0,m]n×mk×kGitter (von ungleichmäßigen Rechtecken) mit mindestens 2. Natürlich haben die Ecken jedes Rechtecks ​​nur ganzzahlige Koordinaten.k

Die Laufzeit des Algorithmus ist durch eine Konstante multipliziert mit der Summe der Perimeter aller dieser Rechtecke über den Rechtecken begrenzt. (Dies liegt daran, dass die Zeit innerhalb jedes Aufrufs O (n + m) beträgt und der Umfang des entsprechenden Rechtecks beträgt .)2(n+m)

Ich behaupte, dass in jedem Satz von Rechtecken, wie oben beschrieben, die Summe der Perimeter höchstens 12 n beträgt . Wenn dies zutrifft, ist dies das Lemma.12nm

Um die Behauptung zu beweisen, beachten Sie zunächst, dass der Umfang des Elternteils für jedes Elternrechteck höchstens das 2/3-fache des Gesamtumfangs der Kinder beträgt , da ist. (Der Umfang des Elternteils beträgt 2 ( n + m ) . Der Gesamtumfang der Kinder beträgt ( 1 + k ) ( n + m ) und k > = 2. )k22(n+m)(1+k)(n+m)k>=2

Daraus folgt , durch ein Standard - Lade Argument , dass der Gesamt perimiter aller Rechtecken höchstens - facht den perimiter von nur die Blattrechtecke. (Die Beobachtung impliziert , dass P N( 2 / 3 ) P T , wobei P N ist der Gesamtumfang der Nicht-Blatt - Rechtecke und P T ist der Gesamtumfang aller Rechtecken. Dies bedeutet(1+2/3+(2/3)2+)=3PN(2/3)PTPNPTist der Gesamtumfang der Blattrechtecke.) und P T - P N.PT3(PTPN)PTPN

Beachten Sie als nächstes, dass die Blattrechtecke das ursprüngliche Rechteck unterteilen. Der maximal mögliche Umfang der Blätter wird erhalten, wenn die Blätter den Einheitsquadraten mit ganzzahligen Endpunkten entsprechen. In diesem Fall beträgt der Gesamtumfang der Blättern×m . Somit beträgt die Summe der Perimeter höchstens 3 4nm , das heißt höchstens 1234nm12nm .

Dies beweist Lemma 1.

Folgerung: Der ursprüngliche Algorithmus läuft in Zeit in Erwartung.O(nm)

Beweis. Wenn die Partition wählt , wird nur das Rechteck dupliziert. Da n > 1 ist , beträgt die Wahrscheinlichkeit, dass k = 1 ist, höchstens 1/2. Somit beträgt die erwartete Häufigkeit, mit der jedes Rechteck dupliziert wird, höchstens 1 (und die erwartete Anzahl von Kopien jedes Rechtecks ​​beträgt höchstens 2). Somit ist für den ursprünglichen Algorithmus die erwartete Summe der Perimiter aller Rechtecke höchstens doppelt so groß wie die des modifizierten Algorithmus, dh höchstens 24 nk=1n>1k=1 . Genau wie bei der Analyse dieses Algorithmus ist die Laufzeit proportional zu dieser Summe, ebenso wie O ( n24nm . QEDO(nm)

Logische Folge. Die Grenze gilt auch mit hoher Wahrscheinlichkeit (vorausgesetzt, sowohl als auch m tendieren zur Unendlichkeit).nm

Beweisskizze. Wenn jede zufällige Auswahl mit Ausnahme der Anzahl der Duplikate jedes Rechtecks ​​festgelegt wird, ist die Zeit proportional zu wobei R die Menge der erzeugten Rechtecke ist, X r die Häufigkeit ist, mit der r dupliziert wird (dh Zeiten, in denen k = 1 für dieses Rechteck ist), und | r | ist der Umfang von r

rR(1+Xr)|r|
RXrrk=1|r|r .

Die Variablen sind unabhängig und jeweils | r | ist O ( n + m ) = o ( n m ) , so dass nach einer Standard-Chernoff-Grenze die Wahrscheinlichkeit, dass die Summe das Doppelte ihrer Erwartung überschreitet, o ( 1 ) ist . (Genauer gesagt, nimm Y r = ( 1 + X r ) | r | / 2 ( n +){Xr:rR}|r|O(n+m)=o(nm)o(1) , dann wende Chernoff auf die Summe der Y r an .) QEDYr=(1+Xr)|r|/2(n+m)Yr


Nebenbei: Wenn der Algorithmus zufällig bis zu min wählen würde (k anstelle von min ( c , n )und dann O ( m n ) in jedem Aufruf arbeiten würde (anstelle von O ( m + n ) ) würde die Gesamtzeiterwartungsgemäßimmer noch O ( m n ) betragen.min(n,m)min(c,n)O(mn)O(m+n)O(mn)

Beweis.Beachten Sie zunächst, dass die Gesamtzeit proportional zur Summe der Flächen aller Rechtecke wäre. Diese Summe entspricht der Summe der Anzahl der Rechtecke, in denen ( i , j ) vorkommt , über die ganzzahligen Koordinaten . Dies ist O ( n m ) in Erwartung, weil in Erwartung jedes gegebene ( i , j) ) im ursprünglichen Rechteck tritt in O ( 1 ) Rechtecken auf. (i,j)(i,j)O(nm)(i,j)O(1)

Um dies zu sehen, nehmen wir an, dass in einem Rechteck r enthalten ist , und betrachten Sie den Aufruf zur Partitionierung auf r . Sei q ( r ) = min ( n ) q ( r ) . Unter dieser Bedingung ist E [ q ( r(i,j)rr . Sei r ' das Rechteck, das das Kind (mit ( i , j ) ) von r ist . MitWahrscheinlichkeit von mindestens 1 / 3 , k mindestens so gewählt , ( 2 / 3q(r)=min(nr,mr)r(i,j)r1/3k(2/3)q(r) , also mitkonstanten Wahrscheinlichkeit q ( r ' ) ist höchstens 1. Wenn das passiert, dann r ' ist ein Blatt (keine Kinder). Daraus folgt, dass die erwartete Anzahl von Rechtecken, in denen sich ( i , j ) befindet, O ( 1 ) ist . QEDE[q(r)]3/2q(r)r(i,j)O(1)

(Ob die -Bindung mit hoher Wahrscheinlichkeit gelten würde, ist eine interessante Frage. Ich denke, das würde es. Sicherlich würde O ( n m log ( n m ) ) whp halten.)O(nm)O(nmlog(nm))

Neal Young
quelle
Vielen Dank, das ist wirklich eine interessante und clevere Idee. Nur als Randnotiz können wir Ihre Idee zum Partitionieren von d-dimensionalen Arrays verwenden. Genau in dem Teil, von dem Sie sagten, dass Kinder ein Gitter erstellen, teilen sie die Eltern tatsächlich in einK×K -Teile von Rechtecken, nicht notwendige Teile gleicher Größe, sodass sie kein Raster erstellen, aber Ihr 2 / 3- Argument gilt immer noch für den Umfang von Eltern über insgesamt Kinder. Ich konnte auch nicht verstehen, wie wir O ( m + n ) durch O ( m n ) als zusätzliche Kosten für jeden Laufersetzen, trotzdem haben wir O (K22/3O(m+n)O(mn) Gesamtlaufzeit. Nochmals vielen Dank für die sehr clevere Idee. O(mn)
Saeed
Bitte! Ich werde den Beweis bearbeiten, um die Punkte zu klären, die Sie ansprechen.
Neal Young
Schöne Klarstellung und gute Frage am Ende, vielen Dank.
Saeed
4

Der typische Ansatz besteht darin, den erwarteten Wert der Laufzeiten des Algorithmus zu analysieren. In diesem Fall ist der erwartete Wert der Laufzeit bei jedem Problem mit , ist so etwas wie k 2 mal die erwartete Laufzeit der Subprobleme partition [ A i , B j ]. Für jedes i , j ist die Größe des Teilproblems eine Zufallsvariable.m,nk2Ai,Bji,j

Die Länge der Liste ist die Differenz zwischen der i- ten und der i + 1- ten Ordnungsstatistik, wenn k Elemente aus { 1 , . . . , m } . Dies ist im Wesentlichen m & bgr; ( k , m + k + 1 ) (dh ist m mal ein Zug aus einer & bgr; ( 1 , m + k + 1 ) Zufallsvariablen). Daher haben wirAiii+1k{1,...,m}mβ(k,m+k+1)mβ(1,m+k+1)

T[m,n|k]]=C.(m+n)+k2x,yT.(mx,ny)xk- -1yk- -1(1- -x)m+k- -1(1- -y)n+k- -1β(k,n+k+1)β(k,m+k+1)dxdy

Hier gibt es einen Rundungsfehler, da wir wirklich im Integranden haben sollten.T.(mx,ny)

Leider ist eine Zufallsvariable, daher muss man auch darüber integrieren. Ich glaube nicht, dass es sinnvoll ist, k n zu fordern , als ob k n Sie die Daten einfach in Unterlisten aufteilen würden, die möglicherweise leer sind. Sagen wir also, k wird gleichmäßig zufällig aus 1 , , c gewählt . Dann erhalten Siekknknk1,,c

T[m,n]=C(m+n)+k=1ck2cx,yT(mx,ny)xk1yk1(1x)m+k1(1y)n+k1β(k,n+k+1)β(k,m+k+1)dxdy

Diese Wiederholung ist ziemlich schrecklich, aber wenn Sie eine Vermutung für eine Grenze für (ich nehme an, T ( m , n ) =T[m,n] ), können Sie Stecken Sie es ein und überprüfen Sie es.T(m,n)=O((logm+logn)(m+n))

David Harris
quelle