Como analisar um algoritmo recursivo randomizado?

8

Considere o seguinte algoritmo, em que é uma constante fixa.cc

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.
}

Qual é o tempo de execução esperado desse algoritmo? O tempo de execução parece ser , mas não consigo encontrar a prova disso.O ( m n )O(mn)

Se, em vez disso, particionássemos as listas de entrada em partes diferentes de igual comprimento, teríamos a recorrência com caso base ; não é difícil provar que . Mas o algoritmo particiona a entrada em um número aleatório de partes com tamanhos aleatórios . (Como sempre, "aleatório" é uma abreviação de "uniformemente aleatório".) Como alguém analisa esse algoritmo?k kT ( n , m ) = k 2T ( n / k , m / k ) + O ( n + m ) T(n,m)=k2T(n/k,m/k)+O(n+m)T ( 1 , n ) = T ( m , 1 ) = O ( 1 ) T(1,n)=T(m,1)=O(1)T ( n , m ) = O ( m n )T(n,m)=O(mn)

Saeed
fonte
Seu algoritmo chamado partição é do tipo lista -> lista -> nula, mas parece-me que em sua última chamada do algoritmo ela tem o tipo -> -> nula? Estou entendendo mal alguma coisa? ' uma' uma' uma' uma
Gopi
8
A pergunta está mal escrita, mas por baixo dela há uma pergunta genuína sobre a análise de recorrências aleatórias.
Suresh Venkat
5
Edição principal. Espero ter preservado o sentido da pergunta.
Jeffε
1
@ Jɛ ff E agora você deve respondê-la :)
Suresh Venkat
1
Você já olhou o artigo de Chaudhuri-Dubhashi sobre recorrências probabilísticas (isso desenvolve ainda mais o trabalho original de Karp sobre esse problema): sciencedirect.com/science/article/pii/S0304397596002617
Suresh Venkat

Respostas:

9

Aqui está uma prova de que esse algoritmo é executado em tempo em expectativa e com alta probabilidade.O ( nm )O(nm)

Primeiro, considere o algoritmo modificado para que seja escolhido em vez de aleatoriamente em .k { 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, independentemente das escolhas aleatórias do algoritmo, o tempo é sempre .O ( nm )O(nm)

Prova. Corrija uma entrada e e corrija arbitrariamente as escolhas aleatórias do algoritmo. Em cada chamada (possivelmente recursiva) para partição (), os dois argumentos correspondem, respectivamente, a dois subarrays: uma sub-disposição de e uma sub-disposição de . Identifique essa chamada com o retângulo . Portanto, a chamada de nível superior é , e cada chamada recursiva corresponde a um sub-retângulo nesseA [ 1 .. n ] B [ 1 .. m ] A [ i 1 . . i 2 ] A B [ j 1 . . j 2 ] B [ i 1 - 1 , i 2 ] × [ j 1 - 1 , j 2 ] [ 0 , n ] × [ 0 , m ] nA[1..n]B[1..m]A[i1..i2]AB[j1..j2]B[i11,i2]×[j11,j2][0,n]×[0,m]× m k × k kn×mretângulo. Esses retângulos formam uma árvore, onde o retângulo correspondente a uma chamada tem como filhos os retângulos que correspondem às chamadas feitas diretamente por essa chamada. Cada retângulo pai é particionado por seus retângulos filhos, que formam uma grade (de retângulos não uniformes) com pelo menos 2. É claro que os cantos de cada retângulo têm apenas coordenadas inteiras.k×kk

O tempo de execução do algoritmo é limitado por uma constante vezes a soma, sobre os retângulos, dos perímetros de todos esses retângulos. (Isso ocorre porque o tempo em cada chamada é O (n + m) e o perímetro do retângulo correspondente é .)2 ( n + m )2(n+m)

Afirmo que em qualquer conjunto de retângulos como descrito acima, a soma dos perímetros é no máximo . Se for verdade, isso prova o lema.12 nm12nm

Para provar a afirmação, observe primeiro que, como , para qualquer retângulo pai, o perímetro do pai é no máximo 2/3 vezes o perímetro total dos filhos. (O perímetro do pai é . O perímetro total das crianças é , e ).k 2 2 ( n + m ) ( 1 + k ) ( n + m ) k > = 2k22(n+m)(1+k)(n+m)k>=2

Segue-se por um argumento de cobrança padrão que o perimitro total de todos os retângulos é no máximo vezes o perimitro apenas dos retângulos foliares . (A observação implica que , onde é o perímetro total dos retângulos que não são folhas e é o perímetro total de todos os retângulos. Isso implica , e é o perímetro total dos retângulos foliares.)( 1 + 2 / 3 + ( 2 / 3 ) 2 + ... ) = 3 P N( 2 / 3 ) P T P N P T P T3 ( P T - P N ) P T - P N(1+2/3+(2/3)2+)=3PN(2/3)PTPNPTPT3(PTPN)PTPN

Em seguida, observe que os retângulos de folhas particionam o retângulo . O perímetro máximo possível das folhas é obtido quando as folhas correspondem aos quadrados da unidade com pontos finais inteiros; nesse caso, o perímetro total das folhas é . Assim, a soma dos perímetros é no máximo , ou seja, no máximo .n × m 4n×mnm 3 44nmnm 12 n34nmm12nm

Isso prova o lema 1.

Corolário: O algoritmo original é executado em no tempo esperado.O ( nm )O(nm)

Prova. Se a partição escolher , apenas duplicará o retângulo. Como , a probabilidade de que seja no máximo 1/2. Assim, o número esperado de vezes que cada retângulo é duplicado é no máximo 1 (e o número esperado de cópias de cada retângulo é no máximo 2). Assim, para o algoritmo original, a soma esperada dos perimitros de todos os retângulos é no máximo duas vezes a do algoritmo modificado, ou seja, no máximo . Assim como na análise desse algoritmo, o tempo de execução é proporcional a essa soma, assim como . QEDk = 1 n > 1 k = 1 24 nk=1n>1k=1m O ( n24nmm )O(nm)

Corolário. O limite também se mantém com alta probabilidade (assumindo que e tendem ao infinito).n mnm

Esboço de prova. Corrigindo todas as opções aleatórias, exceto o número de duplicatas de cada retângulo, o tempo é proporcional a onde é o conjunto de retângulos gerados, é o número de vezes que é duplicado (isto é, quando para esse retângulo) eé o perímetro de .Σ r R (1+Xr)| r| RXrrk=1| r| r

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

As variáveis são independentes e cadaé ; portanto, por um limite Chernoff padrão, a probabilidade de que a soma exceda o dobro de sua expectativa é . (Mais especificamente, pegue e aplique Chernoff à soma dos 's.) QED{ X r : r R } | 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 um aparte: se o algoritmo escolher aleatoriamente até vez de e, em seguida, funcionará em cada chamada (em vez de ), o tempo total ainda seria na expectativa.k min ( n , m ) min ( c , n ) O ( m n ) O ( m + n ) O ( m n )kmin(n,m)min(c,n)O(mn)O(m+n)O(mn)

Prova. Primeiro, observe que o tempo total seria proporcional à soma das áreas de todos os retângulos. Essa soma é igual à soma, sobre as coordenadas inteiras , do número de retângulos nos quais ocorre. Esse é na expectativa porque, na expectativa, qualquer dado no retângulo original ocorre em retângulos . ( i , j ) ( i , j ) O ( n m ) ( i , j ) O ( 1 )(i,j)(i,j)O(nm)(i,j)O(1)

Para ver isso, suponha que esteja contido em um retângulo e considere a chamada para particionar em . Seja . Seja o retângulo que é o filho (contendo ) de . Com probabilidade de pelo menos , é escolhido para ser pelo menos . Com essa condição, , portanto, com probabilidade constante é no máximo 1. Se isso acontecer, então é uma folha (não tem filhos). Daqui resulta que o número esperado de retângulos que( I , j ) r r Q ( r ) = min ( n r , m r ) r ' ( i , j ) r 1 / 3 K ( 2 / 3 ) q ( R ) E [ Q ( r ' ) ] 3 / 2 q ( r ' ) R ' ((i,j)rrq(r)=min(nr,mr)r(i,j)r1/3k(2/3)q(r)E[q(r)]3/2q(r)ri , j ) O ( 1 )(i,j)está em é . QEDO(1)

(Se o limite de se manteria com alta probabilidade é uma questão interessante. Eu acho que sim. Certamente suportaria whp)O ( n m ) O ( n m log ( n m ) )O(nm)O(nmlog(nm))

Neal Young
fonte
Muito obrigado, essa é uma idéia realmente interessante e inteligente. Apenas para uma observação, podemos usar sua ideia para particionar um array tridimensional. Quase na parte que você disse que as crianças estão fazendo , na verdade elas dividem o pai em parte dos retângulos, não são necessárias partes do mesmo tamanho, então elas não fazem uma grade, mas ainda assim o seu argumento é sobre perímetros dos pais sobre o total de filhos. Também não consegui entender como, se substituirmos por como custo extra de cada execução, ainda temos o tempo total de execução de . Mais uma vez, muito obrigado pela idéia muito inteligente. K × K K 2 2 / 3 O ( m + n ) S ( m n ) S ( m n )K×KK22/3O(m+n)O(mn)O(mn)
Saeed
De nada! Vou editar a prova para esclarecer os pontos que você levanta ..
Neal Young
Bom esclarecimento e boa pergunta no final, muito obrigado.
Saeed
4

A abordagem típica é analisar o valor esperado dos tempos de execução do algoritmo. Nesse caso, o valor esperado do tempo de execução, em qualquer problema com , é algo como vezes o tempo de execução esperado da partição de subproblemas [ ]. Para cada o tamanho do subproblema é uma variável aleatória.m , n k 2 A i , B j i , jm,nk2Ai,Bji,j

O comprimento da lista é a diferença entre o th e th estatísticas de ordem quando elementos são elaborados a partir de uar . Isso é essencialmente (isto é, vezes um desvio de uma variável aleatória ). Por isso, temosUm i i i + 1 k { 1 , . . . , m } m β ( k , m + k + 1 ) m β ( 1 , m + k + 1 )Aiii+1k{1,...,m}mβ(k,m+k+1)mβ(1,m+k+1)

T [ m , n | k ] = C ( m + n ) + k 2 x , y T ( m x , n y ) x k - 1 y k - 1 ( 1 - x ) m + k - 1 ( 1 - y ) n + k - 1β ( k , n + k + 1 ) β ( k , m + k + 1 ) dxdy

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

Há algum erro de arredondamento aqui, pois deveríamos realmente ter no integrando.T ( m x , n y )T(mx,ny)

Infelizmente, é uma variável aleatória, portanto, é preciso também integrar sobre ela. Eu não acho que exista motivo para exigir , como se você simplesmente particionasse os dados em sub-listas que podem estar vazias. Digamos que seja escolhido uniformemente aleatoriamente entre . Então você obtémk k n k n k 1 , , ckknknk1,,c

T [ m , n ] = C ( m + n ) + c k = 1 k 2cx,yT(mx,ny)x k - 1 y k - 1 (1-x) m + k - 1 (1-y) n + k - 1β ( k , n + k + 1 ) β ( k , m + k + 1 ) dxdy

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

Essa recorrência é bastante horrível, mas se você adivinhar um limite para (suponho que ) você pode conectá-lo e verificá-lo.T [ m , n ] T ( m , n ) = O ( ( log m + log n ) ( m + n ) )T[m,n]T(m,n)=O((logm+logn)(m+n))

David Harris
fonte