Considere el siguiente algoritmo, donde es una constante fija.
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.
}
¿Cuál es el tiempo de ejecución esperado de este algoritmo? El tiempo de ejecución parece ser , pero no puedo encontrar la prueba de esto.
Si en su lugar dividimos las listas de entrada en diferentes partes de igual longitud, tendríamos la recurrencia con caso base ; No es difícil demostrar que . Pero el algoritmo divide la entrada en un número aleatorio de partes con tamaños aleatorios . (Como de costumbre, "aleatorio" es la abreviatura de "uniformemente al azar"). ¿Cómo se analiza un algoritmo de este tipo?
Respuestas:
Aquí hay una prueba de que este algoritmo se ejecuta en tiempo en expectativa y con alta probabilidad.O(nm)
Primero considere el algoritmo modificado para que sea elegido en lugar de aleatoriamente en .{ 2 , 3 , . . , Min ( c , n ) } { 1 , 2 , . . . , min ( c , n ) }k {2,3,..,min(c,n)} {1,2,...,min(c,n)}
Lema 1. Para este algoritmo modificado, independientemente de las elecciones aleatorias del algoritmo, el tiempo siempre es .O(nm)
Prueba. una entrada y y arregle las elecciones aleatorias del algoritmo arbitrariamente. En cada llamada (posiblemente recursiva) a la partición (), los dos argumentos corresponden respectivamente a dos submatrices: un subconjunto de y una submatriz de . Identifique dicha llamada con el rectángulo . Por lo tanto, la llamada de nivel superior es , y cada llamada recursiva corresponde a un sub-rectángulo dentro de esteB [ 1 .. m ] A [ i 1 . . i 2 ] A B [ j 1 . . j 2 ]A[1..n] B[1..m] A[i1..i2] A B[j1..j2] [ i 1 - 1 , i 2 ] × [ j 1 - 1 , j 2 ] [ 0 , n ] × [ 0 , m ] nB [i1−1,i2]×[j1−1,j2] [0,n]×[0,m] k × k kn×m rectángulo. Estos rectángulos forman un árbol, donde el rectángulo correspondiente a una llamada tiene como hijos los rectángulos que corresponden a las llamadas realizadas directamente por esa llamada. Cada rectángulo principal está dividido por sus rectángulos secundarios, que forman una cuadrícula (de rectángulos no uniformes) con al menos 2. Por supuesto, las esquinas de cada rectángulo tienen solo coordenadas enteras.k×k k
El tiempo de ejecución del algoritmo está limitado por una constante por la suma, sobre los rectángulos, de los perímetros de todos estos rectángulos. (Esto se debe a que el tiempo dentro de cada llamada es O (n + m), y el perímetro del rectángulo correspondiente es .2(n+m)
Afirmo que en cualquier conjunto de rectángulos como se describió anteriormente, la suma de los perímetros es como máximo . Si es cierto, esto prueba el lema.12nm
Para probar la afirmación, observe primero que, debido a que , para cualquier rectángulo principal, el perímetro de los padres es como máximo 2/3 veces el perímetro total de los hijos. (El perímetro de los padres es . El perímetro total de los niños es y )2 ( n + m ) ( 1 + k ) ( n + m ) k > = 2k≥2 2(n+m) (1+k)(n+m) k>=2
Se sigue por un argumento de carga estándar que el perímetro total de todos los rectángulos es como máximo veces el perímetro de solo los rectángulos de hoja . (La observación implica que , donde es el perímetro total de los rectángulos sin hojas y es el perímetro total de todos los rectángulos. Esto implica , y es el perímetro total de los rectángulos de las hojas).P N ≤ ( 2 / 3 ) P T P N P T P T ≤ 3 ( P T - P N ) P T - P N(1+2/3+(2/3)2+…)=3 PN≤(2/3)PT PN PT PT≤3(PT−PN) PT−PN
A continuación, observe que los rectángulos de hoja dividen el rectángulo . El perímetro máximo posible de las hojas se obtiene cuando las hojas corresponden a los cuadrados unitarios con puntos finales enteros, en cuyo caso el perímetro total de las hojas es . Por lo tanto, la suma de los perímetros es como máximo , es decir, como máximo .4n×m 3 ⋅ 44nm 12 n3⋅4nm 12nm
Esto prueba Lemma 1.
Corolario: el algoritmo original se ejecuta en tiempo en expectativa.O(nm)
Prueba. Si la partición elige , simplemente duplica el rectángulo. Como , la probabilidad de que sea como máximo 1/2. Por lo tanto, el número esperado de veces que se duplica cada rectángulo es como máximo 1 (y el número esperado de copias de cada rectángulo es como máximo 2). Por lo tanto, para el algoritmo original, la suma esperada de los perimitros de todos los rectángulos es como máximo dos veces la del algoritmo modificado, es decir, como máximo . Al igual que en el análisis de ese algoritmo, el tiempo de ejecución es proporcional a esta suma, también lo es . QEDn > 1 k = 1 24 nk=1 n>1 k=1 O ( n24nm O(nm)
Corolario. El límite también se mantiene con alta probabilidad (suponiendo que tanto como tienden al infinito).mn m
Bosquejo de prueba. Arreglando cada elección aleatoria, excepto el número de duplicados de cada rectángulo, el tiempo es proporcional a donde es el conjunto de rectángulos generados, es el número de veces que se duplica (es decir, veces cuando para ese rectángulo), yes el perímetro de .RXrrk=1| r| r
Las variables son independientes, y cadaes , por lo que, según un límite estándar de Chernoff, la probabilidad de que la suma exceda el doble de su expectativa es . (Más específicamente, tome , luego aplique Chernoff a la suma de los 's.) QED| r | O ( n + m ) = o ( n m ) o ( 1 ) Y r = ( 1 + X r ) | r | / 2 ( n + m ) Y r{Xr:r∈R} |r| O(n+m)=o(nm) o(1) Yr=(1+Xr)|r|/2(n+m) Yr
Como comentario aparte: si el algoritmo eligiera al azar hasta lugar de y luego haga trabajar en cada llamada (en lugar de ), el tiempo total seguiría siendo en expectativa.min ( n , m ) min ( c , n ) O ( m n ) O ( m + n ) O ( m n )k min(n,m) min(c,n) O(mn) O(m+n) O(mn)
Prueba. Primero tenga en cuenta que el tiempo total sería proporcional a la suma de las áreas de todos los rectángulos. Esta suma es igual a la suma, sobre las coordenadas enteras , del número de rectángulos en los que ocurre. Esto es en expectativa porque, en expectativa, cualquier dado en el rectángulo original ocurre en rectángulos. ( i , j ) O ( n m ) ( i , j ) O ( 1 )(i,j) (i,j) O(nm) (i,j) O(1)
Para ver esto, suponga que está contenido en un rectángulo , y considere la llamada a la partición en . Deje . Sea el rectángulo que es el hijo (que contiene ) de . Con una probabilidad de al menos , se elige para que sea al menos . Condicionado a eso, , entonces con probabilidad constante es como máximo 1. Si eso sucede, entonces es una hoja (no tiene hijos). De esto se deduce que el número esperado de rectángulos quer r q ( r(i,j) r r r ' ( i , j ) r 1 / 3 k ( 2 / 3 ) q ( r ) E [ qq(r)=min(nr,mr) r′ (i,j) r 1/3 k (2/3)q(r) q ( r ' ) r ' (E[q(r′)]≤3/2 q(r′) r′ O ( 1 )(i,j) está en is . QEDO(1)
(Si el límite se mantendría con alta probabilidad es una pregunta interesante ... Creo que lo sería. Ciertamente, mantendría whp)O ( n m log ( n m ) )O(nm) O(nmlog(nm))
fuente
El enfoque típico es analizar el valor esperado de los tiempos de ejecución del algoritmo. En este caso, el valor esperado del tiempo de ejecución, en cualquier problema con , es algo así como veces el tiempo de ejecución esperado de la partición de subproblemas [ ]. Para cada el tamaño del subproblema es una variable aleatoria.k 2 A i , B j i , jm,n k2 Ai,Bj i,j
La longitud de la lista es la diferencia entre el º y th estadísticas de orden cuando elementos se dibujan UAR de . Esto es esencialmente (es decir, es veces un sorteo de una variable aleatoria ). Por lo tanto tenemos i i + 1 k { 1 , . . . , m } m β ( kAi i i+1 k {1,...,m} mβ(k,m+k+1) m β(1,m+k+1)
Aquí hay algún error de redondeo, ya que realmente deberíamos tener en el integrando.T(⌈mx⌉,⌈ny⌉)
Lamentablemente, es una variable aleatoria, por lo que también se debe integrar sobre ella. No creo que tenga sentido exigir , ya que si simplemente dividirá los datos en sublistas que pueden estar vacías. Entonces, digamos que se elige uniformemente al azar entre . Entonces obtienesk k≤n k≥n k 1,…,c
Esta recurrencia es bastante horrible, pero si tiene una conjetura para un límite en (supongo que ) puedes enchufarlo y verificarlo.T ( m , n ) = O ( ( log m + log n ) ( m + n ) )T[m,n] T(m,n)=O((logm+logn)(m+n))
fuente