Relasi Rekurensi

Relasi rekurensi menyatakan waktu eksekusi suatu algoritma rekursif dalam kaitannya dengan waktu eksekusinya pada masukan yang lebih kecil; penyelesaiannya menghasilkan batas asimtotik bentuk tertutup yang digunakan untuk menganalisis algoritma divide-and-conquer dan algoritma rekursif lainnya.

Definition

Relasi rekurensi adalah persamaan yang mendefinisikan nilai suatu fungsi pada suatu masukan dalam kaitannya dengan nilainya pada masukan yang lebih kecil; dalam analisis algoritma, ini menyatakan biaya algoritma pada masukan berukuran n dalam kaitannya dengan biayanya pada submasalah yang lebih kecil.

Scope

Topik ini mencakup formulasi dan penyelesaian rekurensi yang muncul dalam analisis algoritma: metode substitusi, metode pohon rekursi, dan teorema master untuk rekurensi divide-and-conquer dengan bentuk T(n) = aT(n/b) + f(n). Ini menjelaskan bagaimana setiap algoritma rekursif menginduksi suatu rekurensi dan bagaimana menerjemahkan rekurensi tersebut ke dalam batas big-Theta. Ini tidak mencakup notasi asimtotik itu sendiri, yang dibahas secara terpisah, dan metode fungsi pembangkit kombinatorial dari matematika diskrit.

Core questions

• Bagaimana algoritma rekursif memunculkan rekurensi untuk waktu eksekusinya?
• Bagaimana metode substitusi digunakan untuk membuktikan dan memverifikasi solusi yang ditebak?
• Bagaimana metode pohon rekursi menunjukkan total pekerjaan di seluruh tingkat rekursi?
• Kapan teorema master berlaku, dan apa arti ketiga kasusnya?
• Bagaimana rekurensi yang berada di luar bentuk teorema master ditangani?

Key concepts

• relasi rekurensi
• metode substitusi
• metode pohon rekursi
• teorema master
• rekurensi divide-and-conquer
• kasus dasar dan kasus rekursif
• solusi bentuk tertutup
• metode Akra-Bazzi

Key theories

Teorema master

Untuk rekurensi divide-and-conquer T(n) = aT(n/b) + f(n), teorema master memberikan solusi asimtotik dengan membandingkan f(n) dengan n pangkat log basis b dari a, mencakup tiga kasus di mana daun, akar, atau tingkat yang seimbang mendominasi.

Metode pohon rekursi dan substitusi

Metode pohon rekursi menjumlahkan pekerjaan yang dilakukan pada setiap tingkat rekursi untuk menyarankan batas, yang kemudian dibuktikan secara ketat oleh metode substitusi melalui induksi; bersama-sama mereka menangani rekurensi di luar cakupan teorema master.

Clinical relevance

Penyelesaian rekurensi adalah jalur standar untuk menentukan waktu eksekusi algoritma rekursif, mulai dari mergesort dan quicksort hingga perkalian cepat dan banyak program dinamis. Para insinyur dan peneliti secara rutin menggunakan teorema master untuk menurunkan dan membenarkan klaim kompleksitas asimtotik yang melekat pada algoritma tersebut.

History

Analisis rekurensi algoritma disistematisasi dalam buku The Art of Computer Programming karya Knuth. Teorema master menjadi pokok bahasan buku teks melalui CLRS, dan metode Akra-Bazzi (1998) menggeneralisasikannya ke kelas rekurensi divide-and-conquer yang lebih luas dengan pembagian yang tidak merata.

Key figures

• Donald Knuth
• Mohamad Akra
• Louay Bazzi

Seminal works

• cormen2009
• knuth1997vol1

Frequently asked questions

Kapan saya bisa menggunakan teorema master?

Teorema master berlaku untuk rekurensi berbentuk T(n) = aT(n/b) + f(n) dengan a >= 1 dan b > 1, di mana setiap tingkat membagi masalah menjadi a submasalah berukuran n/b. Rekurensi dengan pembagian yang tidak merata, ukuran submasalah yang bervariasi, atau biaya kombinasi non-polinomial mungkin memerlukan metode pohon rekursi, substitusi, atau Akra-Bazzi.

Mengapa rekurensi mergesort menghasilkan O(n log n)?

Mergesort menghasilkan T(n) = 2T(n/2) + O(n): dua submasalah berukuran setengah ditambah penggabungan linier. Di sini pekerjaan per tingkat adalah sama di semua log n tingkat pohon rekursi, sehingga totalnya adalah n kali log n, yang dikonfirmasi oleh teorema master sebagai Theta(n log n).