Apa kompleksitas waktu dari algoritma ini? Dan mengapa?

Saya terjebak dengan menganalisis kompleksitas waktu dari algoritma berikut:

def fun (r, k, d, p):
    if d > p:
        return r
    if d = 0 and p = 0:
        r <- r + k
        return r
    if d > 0:
        fun (r, k + 1, d - 1, p)
    if p > 0:
        fun (r, k - 1, d, p - 1)

Panggilan root akan menjadi fun (0, 0, n, n), dan nmerupakan ukuran masalah.

Saya kira itu: Relasi perulangan adalah $T(n, n) = T(n-1, n) + T(n, n-1)$ , yang setara dengan , dan . $T(2n) = 2T(2n-1) \iff T(m) = 2T(m - 1)$ $O(2^m) \iff O(4^n)$

Apakah analisis saya benar (saya tahu itu tidak terlalu lengkap dan tepat)? Jika memang ada cacat serius, tunjukkan atau tunjukkan saya bukti yang benar dan lengkap tentang kompleksitas waktu dari algoritma ini.

algorithm-analysis runtime-analysis 象嘉道
sumber

xando, saya mendorong Anda untuk mengedit pertanyaan untuk menjelaskan mengapa teknik standar tidak berfungsi: jelaskan mengapa mereka gagal. (Cc: @YuvalFilmus) Misalnya, apakah Anda mendapatkan relasi perulangan yang sulit diselesaikan, dan jika demikian, perulangan apa yang Anda dapatkan?

Dalam komentar dengan Polyergic, saya telah menyadari bahwa kodesemu tidak jelas: tidak jelas apa yang Anda maksud untuk algoritma lakukan, kapan keduanya d>0dan p>0. Anda tidak menunjukkan apa fungsi kembali jika kita mencapai pernyataan if ke-3 dan ke-4. Apakah Anda bermaksud memiliki returnpernyataan setelah setiap doa rekursif fun? (Apakah Anda bermaksud fun (r, k + 1, d - 1, p)menjadi return fun (r, k + 1, d - 1, p)?) Atau apakah Anda bermaksud memiliki returnpernyataan di akhir fungsi tubuh? Harap edit kodesemu Anda untuk memperjelas dan memastikan Anda menunjukkan apa yang dikembalikan dalam semua kasus yang mungkin.

Untuk mengatakannya dengan cara lain: anggap d<=pdan d>0dan p>0semua pegang. Apa yang seharusnya terjadi? Apakah algoritma membuat 2 doa rekursif ke fungsi? Atau apakah itu secara rekursif memohon fun(r, k + 1, d - 1, p)dan kemudian segera kembali, tanpa memohon secara rekursif fun(r, k - 1, d, p - 1)? Jika saya mengambil pseudocode Anda secara harfiah, tampaknya itu membuat 2 doa rekursif dan kemudian kembali dengan nilai pengembalian yang tidak ditentukan - tapi itu aneh dan membuat saya bertanya-tanya apakah ada kesalahan ketik / bug dalam pseudocode.

Jawaban:

Dua argumen yang relevan dengan analisis asimptotik adalah $d$ dan $p$ . Argumen-argumen ini (secara virtual) memuaskan $d,p \geq 0$ dan $d \leq p$ (kita perlu mengocok logika dalam fungsi sedikit untuk mendapatkan ini). Di setiap titik dalam eksekusi, Anda mengambil pasangan saat ini $(d,p)$ dan kemudian secara rekursif memanggil fungsi dengan pasangan $(d-1,p),(d,p-1)$ , menghindari pasangan yang membatalkan batasan yang disebutkan di atas.

Kita bisa menggambarkan pohon panggilan yang dihasilkan sebagai jalan mulai dari $(0,0)$ . Setiap kali Anda mengurangi $p$ , tambahkan / langkah. Setiap kali Anda mengurangi $d$ , tambahkan \ langkah. Kondisi $d \leq p$ menjamin bahwa Anda tidak pernah pergi di bawah sumbu X. Selain itu, Anda memiliki "anggaran" sebesar $n$ dari setiap langkah. Jumlah total daun di pohon panggilan ini persis nomor Catalan $\binom{2n}{n}/(n+1) = \Theta(4^n/n^{3/2})$ , dan ini memberi kita batas bawah pada waktu menjalankan fungsi.

Untuk mendapatkan batas atas, perhatikan bahwa dalam perjalanan ke setiap daun yang kita lewati $2n$ node, dan ini memberi batas atas $2n$ lebih besar dari batas bawah, yaitu, $\Theta(4^n/\sqrt{n})$ .

Kami memiliki batas bawah $\Omega(4^n/n^{3/2})$ dan batas atas $O(4^n/\sqrt{n})$ . Apa asimptotik yang tepat? Mereka tumbuh seperti jumlah total jalur yang tidak melewati sumbu X yang paling banyak $n$ langkah di setiap arah. Dengan menggunakan teorema surat suara Bertrand kita bisa mendapatkan ungkapan yang tepat untuk ini:

\sum_{0 \leq d \leq hal \leq n} \frac{hal - d + 1}{hal + 1} (\binom{hal + d}{hal}) .

$\sum_{0 \leq d \leq p \leq n} \frac{p-d+1}{p+1} \binom{p+d}{p}.$ Dengan demikian tetap untuk memperkirakan jumlah ini secara asimptotik:

\sum_{0 \leq d \leq hal \leq n} (\binom{hal + d}{hal}) - \sum_{0 \leq d \leq hal \leq n} \frac{d}{hal + 1} (\binom{hal + d}{d}) = \sum_{0 \leq d \leq hal \leq n} (\binom{hal + d}{hal}) - \sum_{0 \leq d \leq hal \leq n} (\binom{hal + d}{hal + 1}) = \sum_{hal = 0}^{n} (\binom{2 hal + 1}{hal + 1}) - \sum_{hal = 0}^{n} (\binom{2 hal + 1}{hal + 2}) = \sum_{hal = 0}^{n} \frac{1}{hal + 1} (\binom{2 hal + 2}{hal}) = Θ (\sum_{hal = 0}^{n} \frac{4^{hal}}{{hal}^{3 / 2}}) = Θ (\frac{4^{n}}{n^{3 / 2}}) .

$\sum_{0 \leq d \leq p \leq n} \binom{p+d}{p} - \sum_{0 \leq d \leq p \leq n} \frac{d}{p+1} \binom{p+d}{d} = \\ \sum_{0 \leq d \leq p \leq n} \binom{p+d}{p} - \sum_{0 \leq d \leq p \leq n} \binom{p+d}{p+1} = \\ \sum_{p=0}^n \binom{2p+1}{p+1} - \sum_{p=0}^n \binom{2p+1}{p+2} = \\ \sum_{p=0}^n \frac{1}{p+1} \binom{2p+2}{p} = \Theta\left(\sum_{p=0}^n \frac{4^p}{p^{3/2}}\right) = \Theta\left(\frac{4^n}{n^{3/2}}\right).$

Yuval Filmus
sumber

Saya sangat suka pendekatan geometris Anda menggunakan "langkah" ini. Apakah itu teknik yang umum? Saya belum pernah melihatnya sebelumnya.

Andreas T

@ AndrewT Saya tidak akan menyebutnya teknik umum, memang biasanya itu tidak berlaku. Di sini interpretasi kombinatorial cukup jelas, dan itu mengarah pada solusi semacam ini.

Yuval Filmus

Kasus per kasus:

d> p : Waktu konstan
d = 0 ∧ p = 0 : Waktu konstan
d> 0 : Perhatikan bahwa d ≯ p, jadi kita memiliki 0 <d ≤ p, dan funberulang pada d-1 hingga d ≯ 0; sejak p> 0, ini adalah Linear dalam d + (kasus 4) .
p> 0 : Perhatikan bahwa d ≯ 0, jadi kita memiliki d ≤ 0 ≤ p (dengan d <p), dan funberulang pada p-1 hingga p ≯ 0; ini Linear dalam p + (salah satu dari kasus 1, 2, atau 5)
d ≤ p <0 : Tidak terdefinisi; Saya berasumsi ini adalah waktu yang Konstan

Dimulai dengan d = p = n> 0 hits case 3, yang diikuti oleh case 4. Jika n adalah bilangan bulat, case terakhir adalah 2, jika case terakhir adalah 5. Total waktu untuk kasus tersebut adalah d + p +1, atau 2n +1.

ShadSterling
sumber

2n. Saya kira Anda kalah karena saya fokus pada alasan?

ShadSterling

Terima kasih telah mengedit jawabannya! Teka-teki sekarang adalah Anda menyimpulkan bahwa waktu berjalan adalah

O (n)

$O(n)$ , tetapi Yuval menyimpulkan bahwa waktu berjalan adalah eksponensial di

n

$n$ . Itu perbedaan yang cukup besar.

Hmm, saya pikir saya mengambil kodesemu if s untuk menjadi "melakukan salah satu dari ini" sementara @Yuval menganggap mereka "mempertimbangkan masing-masing dalam urutan". Yang terakhir, tentu saja, apa artinya if(tanpa else) dalam kode aktual; Saya terbiasa dengan yang pertama dalam hampir semua konteks selain kode aktual (termasuk dalam pseudocode, meskipun penggunaan dalam pseudocode tidak konsisten).

ShadSterling

Saya mengerti apa yang kamu maksud. Kurangnya returnpernyataan di bagian akhir kode membuat ini sangat membingungkan.