Considere o seguinte algoritmo, em que é uma constante fixa.c
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 )
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
Respostas:
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] A B[j1..j2] B [i1−1,i2]×[j1−1,j2] [0,n]×[0,m] × m k × k kn×m retâ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×k k
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 > = 2k≥2 2(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 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
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×m nm 3 ⋅ 44nm nm 12 n3⋅4nm m12nm
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=1 n>1 k=1 m O ( n24nm m )O(nm)
Corolário. O limite também se mantém com alta probabilidade (assumindo que e tendem ao infinito).n mn m
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
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 )k min(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) r r q(r)=min(nr,mr) r′ (i,j) r 1/3 k (2/3)q(r) E[q(r′)]≤3/2 q(r′) r′ i , 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))
fonte
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,n k2 Ai,Bj i,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 )Ai i i+1 k {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
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 , … , ck k≤n k≥n k 1,…,c
T [ m , n ] = C ( m + n ) + c ∑ k = 1 k 2c ∫x,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
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))
fonte