Bagaimana cara menganalisis algoritma rekursif acak?

Pertimbangkan algoritma berikut, di mana adalah konstanta tetap. $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.
}

Berapa perkiraan waktu berjalan dari algoritma ini? Waktu yang berjalan tampaknya , tetapi saya tidak dapat menemukan buktinya. $O(mn)$

Jika kita sebaliknya mempartisi daftar input menjadi bagian yang berbeda dengan panjang yang sama, kita akan memiliki rekurensi dengan kasus dasar ; tidak sulit untuk membuktikan bahwa . Tapi algoritma partisi masukan ke dalam acak sejumlah bagian dengan acak ukuran. (Seperti biasa, "acak" adalah singkatan untuk "seragam secara acak".) Bagaimana seseorang menganalisis algoritma seperti itu? $k$ $T(n,m) = k^2\,T(n/k,m/k) + O(n+m)$ $T(1,n) = T(m,1) = O(1)$ $T(n,m) = O(mn)$

cc.complexity-theory ds.algorithms randomness randomized-algorithms recursive Saeed
sumber

Algoritme Anda disebut partisi bertipe list -> list -> void, tetapi menurut saya, dalam panggilan terakhir Anda dari algoritma, ia memiliki tipe -> -> void? Apakah saya salah mengerti sesuatu?

^{'} a

$'a$

^{'} a

$'a$

^{'} a

$'a$

^{'} a

$'a$

Gopi

Pertanyaannya ditulis dengan buruk, tetapi di bawahnya ada pertanyaan asli tentang menganalisis pengulangan acak.

Suresh Venkat

Sunting besar. Mudah-mudahan saya telah mempertahankan rasa pertanyaan itu.

Jeffε

@ Jɛ ﬀ E sekarang kamu harus menjawabnya :)

Suresh Venkat

Pernahkah Anda melihat kertas Chaudhuri-Dubhashi tentang kemungkinan berulang (ini mengembangkan lebih lanjut karya asli Karp tentang masalah ini): sciencedirect.com/science/article/pii/S030439759600261717

Suresh Venkat

Jawaban:

Berikut ini adalah bukti bahwa algoritma ini berjalan dalam waktu dalam harapan dan dengan probabilitas tinggi. $O(n\,m)$

Pertama pertimbangkan algoritma yang dimodifikasi sehingga dipilih dalam alih-alih secara acak dalam . $k$ $\{2,3,..,\min(c,n)\}$ $\{1,2,...,\min(c,n)\}$

Lemma 1. Untuk algoritma yang dimodifikasi ini, terlepas dari pilihan acak dari algoritma, waktu selalu . $O(n\,m)$

Bukti. Perbaiki input dan dan perbaiki pilihan acak dari algoritma secara sewenang-wenang. Dalam setiap (mungkin rekursif) panggilan untuk partisi (), dua argumen sesuai masing-masing dua subarrays: a subarray dari dan subarray dari . Identifikasi panggilan seperti itu dengan persegi panjang . Dengan demikian, panggilan tingkat atas adalah , dan setiap panggilan rekursif sesuai dengan sub-persegi panjang dalam $A[1..n]$ $B[1..m]$ $A[i_1..i_2]$ $A$ $B[j_1..j_2]$ $B$ $[i_1-1,i_2] \times [j_1-1,j_2]$ $[0,n]\times[0,m]$ $n\times m$ empat persegi panjang. Persegi panjang ini membentuk pohon, di mana persegi panjang yang sesuai dengan satu panggilan memiliki sebagai anak-anak persegi panjang yang sesuai dengan panggilan yang dibuat langsung oleh panggilan itu. Setiap persegi panjang orang tua dipartisi oleh anak persegi panjangnya, yang membentuk kisi (dari persegi tidak seragam) dengan setidaknya 2. Tentu saja setiap sudut persegi panjang hanya memiliki koordinat bilangan bulat. $k\times k$ $k$

Waktu berjalan dari algoritma dibatasi oleh konstanta kali jumlah, di atas persegi panjang, dari perimeter semua persegi panjang ini. (Ini karena waktu dalam setiap panggilan adalah O (n + m), dan pembatas persegi panjang yang sesuai adalah .) $2(n+m)$

Saya mengklaim bahwa dalam set persegi panjang seperti yang dijelaskan di atas, jumlah perimeter maksimal . Jika benar, ini membuktikan lemma. $12 n\,m$

Untuk membuktikan klaim tersebut, perhatikan terlebih dahulu bahwa, karena , untuk persegi panjang orang tua mana pun, perimeter orang tua paling banyak 2/3 kali perimeter total anak-anak. (Batas orang tua adalah . Batas total anak-anak adalah , dan ) $k \ge 2$ $2(n+m)$ $(1+k)(n+m)$ $k >= 2$

Ini mengikuti dengan argumen pengisian standar bahwa pembatas total semua persegi panjang paling banyak kali pembatas hanya persegi panjang daun . (Pengamatan menyiratkan bahwa , di mana adalah perimeter total persegi panjang non-daun dan adalah perimeter total semua persegi panjang. Ini menyiratkan , dan adalah perimeter total dari persegi panjang daun.) $(1 + 2/3 + (2/3)^2 + \ldots ) = 3$ $P_N \le (2/3) P_T$ $P_N$ $P_T$ $P_T \le 3(P_T-P_N)$ $P_T-P_N$

Selanjutnya, amati bahwa persegi panjang daun mempartisi persegi panjang asli . Perimeter maksimum yang mungkin dari daun diperoleh ketika daun sesuai dengan kuadrat unit dengan titik akhir bilangan bulat, dalam hal ini total perimeter daun adalah . Jadi, jumlah perimeter maksimal , yaitu, paling banyak . $n\times m$ $4\,n\,m$ $3\cdot 4\,n\,m$ $12 n\,m$

Ini membuktikan Lemma 1.

Konsekuensi: Algoritme asli berjalan dalam waktu dengan harapan. $O(n\,m)$

Bukti. Jika partisi memilih , itu hanya akan menduplikasi persegi panjang. Sejak , probabilitas paling banyak 1/2. Dengan demikian, jumlah yang diharapkan dari setiap persegi yang diduplikasi adalah paling banyak 1 (dan jumlah salinan yang diharapkan dari setiap persegi paling banyak 2). Jadi, untuk algoritma asli, jumlah yang diharapkan dari perimiter dari semua persegi panjang paling banyak dua kali lipat dari algoritma yang dimodifikasi, yaitu paling banyak . Sama seperti dalam analisis algoritma itu, waktu berjalan sebanding dengan jumlah ini, demikian juga . QED $k=1$ $n>1$ $k=1$ $24 n\,m$ $O(n\,m)$

Akibat wajar. Batas juga berlaku dengan probabilitas tinggi (dengan asumsi dan cenderung tak terhingga). $n$ $m$

Sketsa bukti. Memperbaiki setiap pilihan acak kecuali jumlah duplikat dari setiap persegi panjang, waktunya sebanding dengan di mana adalah himpunan persegi panjang yang dihasilkan, adalah jumlah kali diduplikasi (yaitu, saat untuk persegi panjang itu), danadalah keliling .

\sum_{r \in R} (1 + X_{r}) | r |

$\sum_{r\in R} (1+X_r) |r|$

R

$R$

X_{r}

$X_r$

r

$r$

k = 1

$k=1$

| r |

$|r|$

r

$r$

Variabel independen, dan masing-masingadalah , jadi dengan standar Chernoff terikat, probabilitas bahwa jumlah melebihi dua kali harapannya adalah . (Lebih khusus, ambil , lalu terapkan Chernoff ke jumlah 's.) QED $\{X_r : r \in R\}$ $|r|$ $O(n+m) = o(n m)$ $o(1)$ $Y_r = (1+X_r) |r|/2(n+m)$ $Y_{r}$

Sebagai tambahan: jika algoritma memilih secara acak hingga alih-alih dan kemudian lakukan bekerja di setiap panggilan (alih-alih ), total waktu akan tetap dalam harapan. $k$ $\min(n,m)$ $\min(c,n)$ $O(m n)$ $O(m+n)$ $O(mn)$

Bukti. Catatan pertama bahwa total waktu akan sebanding dengan jumlah area dari semua persegi panjang. Jumlah ini sama dengan jumlah, di atas koordinat bilangan bulat , dari jumlah persegi panjang yang muncul di. Ini adalah dalam ekspektasi karena, dalam ekspektasi, setiap diberikan dalam persegi panjang asli terjadi di persegi panjang. $(i,j)$ $(i,j)$ $O(nm)$ $(i,j)$ $O(1)$

Untuk melihat ini, misalkan terkandung dalam persegi panjang , dan pertimbangkan panggilan ke partisi pada . Biarkan . Biarkan menjadi persegi panjang yang merupakan anak (mengandung ) dari . Dengan probabilitas setidaknya , dipilih setidaknya . Dengan syarat, , jadi dengan probabilitas konstan paling banyak 1. Jika itu terjadi, maka adalah daun (tidak memiliki anak). Ini mengikuti dari ini bahwa jumlah persegi yang diharapkan $(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')] \le 3/2$ $q(r')$ $r'$ $(i,j)$ is in adalah . QED $O(1)$

(Apakah batas akan berlaku dengan probabilitas tinggi adalah pertanyaan yang menarik .. Saya pikir itu akan. Tentu saja akan menahan whp) $O(nm)$ $O(nm\log(nm))$

Neal Young
sumber

Terima kasih banyak, ini ide yang sangat menarik dan cerdas. Hanya untuk catatan tambahan, kami dapat menggunakan ide Anda untuk mempartisi array d-dimensional. Hanya tentang bagian yang Anda katakan anak-anak membuat grid, sebenarnya mereka membagi orang tua dalam bagian dari persegi panjang, tidak perlu bagian ukuran yang sama, sehingga mereka tidak akan membuat kotak, tetapi argumen Anda masih berlaku perimeter orang tua dari total anak. Juga saya tidak bisa mendapatkan bagaimana jika kita mengganti dengan sebagai biaya tambahan untuk setiap proses, masih kita memiliki total waktu pengoperasian . Sekali lagi terima kasih banyak atas ide yang sangat cerdas.

K \times K

$K\times K$

K^{2}

$K^2$

2 / 3

$2/3$

O (m + n)

$O(m+n)$

O (m n)

$O(mn)$

O (m n)

$O(mn)$

Saeed

Sama-sama! Saya akan mengedit buktinya untuk mengklarifikasi poin yang Anda angkat ..

Neal Young

Klarifikasi yang bagus dan pertanyaan yang bagus pada akhirnya, terima kasih banyak.

Saeed

Pendekatan khas adalah untuk menganalisis nilai yang diharapkan dari waktu berjalan dari algoritma. Dalam kasus ini, nilai yang diharapkan dari waktu berjalan, pada masalah apa pun dengan , adalah sesuatu seperti kali waktu berjalan yang diharapkan dari partisi subproblem [ ]. Untuk setiap ukuran subproblem adalah variabel acak. $m,n$ $k^2$ $A_i,B_j$ $i,j$

Panjang daftar adalah perbedaan antara statistik urutan ke - dan ke- ketika elemen digambar dari . Ini pada dasarnya adalah (yaitu kali undian dari variabel acak ). Karena itu kita punya $A_i$ $i$ $i+1$ $k$ $\{1, ..., m \}$ $m \beta(k,m+k+1)$ $m$ $\beta(1,m+k+1)$

T [m, n | k] = C (m + n) + k^{2} \int_{x, y} T (m x, n y) \frac{x^{k - 1} y^{k - 1} (1 - x)^{m + k - 1} (1 - y)^{n + k - 1}}{β (k, n + k + 1) β (k, m + k + 1)} d x d y

$T[m,n | k] = C (m + n) + k^2 \int_{x,y} T(m x, n y) \frac{x^{k-1} y^{k-1} (1-x)^{m+k-1} (1-y)^{n+k-1}}{\beta(k,n+k+1) \beta(k,m+k+1)} dx dy$

Ada beberapa kesalahan pembulatan di sini, karena kita harus benar-benar memiliki di integrand. $T(\lceil mx \rceil, \lceil ny \rceil)$

Sayangnya adalah variabel acak sehingga kita juga harus berintegrasi dengannya. Saya tidak berpikir ada gunanya meminta , karena jika Anda hanya akan mempartisi data menjadi sub-daftar yang mungkin kosong. Jadi katakanlah dipilih secara seragam secara acak dari . Maka Anda mendapatkan $k$ $k \leq n$ $k \geq n$ $k$ $1,\dots, c$

T [m, n] = C (m + n) + \sum_{k = 1}^{c} \frac{k^{2}}{c} \int_{x, y} T (m x, n y) \frac{x^{k - 1} y^{k - 1} (1 - x)^{m + k - 1} (1 - y)^{n + k - 1}}{β (k, n + k + 1) β (k, m + k + 1)} d x d y

$T[m,n] = C (m + n) + \sum_{k=1}^c \frac{k^2}{c} \int_{x,y} T(m x, n y) \frac{x^{k-1} y^{k-1} (1-x)^{m+k-1} (1-y)^{n+k-1}}{\beta(k,n+k+1) \beta(k,m+k+1)} dx dy$

Perulangan ini cukup mengerikan, tetapi jika Anda memiliki tebakan untuk terikat pada (saya kira ) Anda bisa pasang dan verifikasi. $T[m,n]$ $T(m,n) = O( (\log m + \log n) (m+n) )$

David Harris
sumber