Visualisasi

1. Introduction

Visualisasi ini dapat menggambarkan pohon rekursi dari algoritma rekursif apa pun atau pohon rekursi dari rekursi algoritma Divide and Conquer (D&C) (misalnya, Teorema Master) yang dapat kita tulis secara sah dalam JavaScript.


Visualisasi ini dapat memvisualisasikan pohon rekursi dari sebuah algoritma rekursif.

Kita juga dapat memvisualisasikan Graf Asiklik Berarah (DAG) dari sebuah algoritma Pemrograman Dinamis (DP) dan membandingkan perbedaan tempat pencarian dari sebuah masalah DP versus jika subsoal bertumpukannya dihitung secara seperti rekursi eksponensial Ω(2n/2) Fibonacci versus versi DPnya O(n)n.


Untuk beberapa masalah, kita juga bisa memvisualisasikan perbedaan antara pencarian komplet (backtracking rekursif) yang menjelajahi keseluruhan ruang pencarian, sebuah algoritma greedy (yang memilih sebuah cabang secara greedy tiap kali), versus Pemrograman Dinamis (DP) dalam pohon rekursi yang sama seperti, Coin-Change untuk v = 7 sen dengan 4 koin {4, 3, 1, 5} sen.


Kebanyakan pohon rekursi memerlukan ruang gambar yang besar, maka tampilkan laman visualisasi ini pada screen besar. Untuk alasan yang jelas, kita tidak bisa memvisualisasikan pohon/DAG yang besar. Maka, kita memanggil rekursi dengan parameter kecil.

2. Pohon Rekursi

Ini adalah daerah visualisasi dari Pohon / DAG Rekursi. Pohon / DAG Rekursi digambar/dianimasikan sesuai dengan bagaimana suatu program komputer nyata yang mengimplementasikan rekursi ini bekerja, yaitu "depth-first".


Rekursi dimulai dari keadaan awal yang diberi warna coklat tua. Nilai parameter saat ini ditampilkan di dalam setiap vertex (dipisahkan koma untuk rekursi dengan dua parameter atau lebih). Vertex aktif akan diberi warna oranye. Vertex yang tidak lagi memanggil masalah rekursif lainnya (kasus dasar) akan diberi warna hijau. Vertex (submasalah) yang diulang akan diberi warna biru muda untuk kemunculan kedua dan seterusnya. Nilai kembali dari setiap panggilan rekursif ditulis sebagai teks merah di bawah vertex. Visualisasi ini bersifat umum untuk rekursi apa pun yang dapat Anda tulis secara sah dalam JavaScript.

Dikarenakan ledakan kombinatorial, akan sulit bagi kami untuk memvisualisasikan pohon rekursi berukuran besar.

2-1. DAG Rekursi

Untuk DAG rekursi, akan sangat sulit untuk meminimalkan jumlah persilangan tepi jika terjadi subproblema yang tumpang tindih. Namun, kami berusaha sebaik mungkin untuk memberikan tata letak DAG yang kustom untuk masalah DP tertentu guna meningkatkan penyajian.


Sebagai contoh, saat ini kami menunjukkan DAG Rekursi dari perhitungan angka Fibonacci ke-n. Kami menyusun vertex dari yang paling kiri (kasus dasar hijau n = 0 dan n = 1)hingga yang paling kanan (n awal). Idealnya, ini ditampilkan sebagai array 1-D (memoization) datar. Namun, karena VisuAlgo belum memiliki tepi melengkung, kami memutuskan untuk meletakkan vertex bernomor ganjil sedikit di bawah vertex bernomor genap untuk mengatasi masalah tepi yang tumpang tindih. Untuk menghitung fib(n), kita hanya perlu mengetahui hasil dari dua hasil langsung: fib(n-1) + fib(n-2) yang digambarkan sebagai dua panah dari vertex n ke vertex n-1 dan n-2. Hasil penjumlahan, yaitu nilai setiap fib(n), ditampilkan sebagai teks merah di bawah vertex. Karena tidak ada perhitungan subproblema yang berulang, tidak ada vertex berwarna biru muda sama sekali dalam DAG Rekursi ini (vertex tersebut akan memiliki lebih dari satu panah masuk).

3. Contoh Rekursi - Satu Subsoal

Pilih salah satu algoritma rekursif contoh dalam daftar drop-down atau tulis kode rekursif Anda sendiri — dalam JavaScript. Pohon / DAG rekursi akhir akan langsung ditampilkan. Perhatikan bahwa visualisasi ini dapat menjalankan kode JavaScript apa pun, termasuk kode berbahaya, jadi harap berhati-hati (ini hanya akan mempengaruhi browser web Anda sendiri, jangan khawatir).


Klik tombol 'Mulai' di sudut kanan atas kotak aksi untuk memulai visualisasi langkah demi langkah dari fungsi rekursif setelah Anda memilih (atau menulis) kode JavaScript yang valid!


Pada sub-bagian berikutnya, kita mulai dengan algoritma rekursif contoh yang hanya memiliki satu sub-masalah, yaitu tidak bercabang. Untuk contoh satu-subsoal ini, pohon rekursi dan DAG rekursi mereka 100% identik (mereka terlihat seperti Senarai Berantai Tunggal dari akar (panggilan awal) ke daun (kasus dasar)). Karena tidak ada subsoal yang tumpang tindih untuk contoh dalam kategori ini, Anda tidak akan melihat vertex yang berwarna biru muda dan hanya satu vertex berwarna hijau (kasus dasar). Orientasi default untuk pohon rekursi adalah dari kanan-atas ke kiri-bawah, sedangkan orientasi default untuk DAG rekursi adalah dari kanan ke kiri.

3-1. Bilangan Faktorial

Bilangan Faktorial menghitung faktorial dari sebuah bilangan n.


f(n) = 1 (if n == 0);
f(n) = n*f(n-1) otherwise

Ini adalah salah satu fungsi rekursif (ekor) yang paling sederhana yang dapat dengan mudah ditulis ulang menjadi versi iteratif. Kompleksitas waktunya juga sederhana yaitu Θ(n).


Nilai Faktorial f(n) berkembang sangat cepat, jadi coba hanya bilangan bulat kecil n ∈ [0..10] (kita mengacak nilai awal n dalam rentang ini).

3-2. Pencarian Biner

Contoh pencarian biner ini mencari indeks dari a2 dalam sebuah larik terurut a1[a..b]. Kita memulai pencarian biner dari ruang pencarian awal a=0,b=a1.length-1 (keseluruhan larik a1, dengan n = (a1.length-1) - 0 + 1 = a1.length).


f(a,b) = -1 (if a > b);
let mid = floor((a+b)/2);
f(a,b) = mid (if a2 = a1[mid]);
f(a,b) = f(a,mid-1) (if a2 < a1[mid]);
f(a,b) = f(mid+1,b) (if a2 > a1[mid]);

Hanya salah satu dari dua cabang yang mungkin akan dieksekusi setiap kali, menghasilkan situasi pohon rekursi = DAG rekursi. Kompleksitas waktunya adalah Θ(log n) karena kita terus membagi ruang pencarian setiap kali. Kasus terburuk terjadi ketika a2 tidak ditemukan dalam array terurut a1.


Dalam visualisasi ini, kami mengacak isi larik terurut a1 dan nilai yang akan dicari a2.


TBC: Dalam waktu dekat, kami akan menggambar seluruh ruang pencarian Θ(n) (baik cabang kiri maupun kanan di setiap vertex) dan menyoroti jalur efisien Θ(log n) yang diambil oleh pencarian biner pada ruang pencarian ini. Ini mirip dengan melihat animasi fungsi Cari(v) dari BST (seimbang).

3-3. Pangkat Modulo

Pangkat Modulo menghitung nilai dari a1^p % a2 dengan cara yang efisien.


f(p) = 1 (if p == 0);
f(p) = f(floor(p/2))^2 % a2 (if p genap)
f(p) = f(floor(p/2))^2 * a1 % a2 (if p ganjil)

Algoritma D&C ini berjalan dalam Θ(log p).


Dalam visualisasi ini, kita mengacak nilai a1 (basisnya, sebuah nilai kecil ∈ [2..4]),
a2 (modulo, sebuah bilangan prima ∈ [7, 97, 997, 9973]), dan pangkat p (kita mau memangkatkan a1 sebanyak p, modulo a2. Karena kompleksitas waktu yang kecil, tidak ada masalah untuk mencoba nilai besar 0 ≤ p ≤ 256.


TBC: Di waktu dekat, kita mungkin menggambarkan perbandingan antara algoritma pangkat modulo efisien ini dengan versi naif yang mengalikan a1 p kali yang berjalan dalam Θ(p).

3-4. Faktor Persekutuan Terbesar (FPB)

Faktor Persekutuan Terbesar (FPB) menghitung FPB dari dua bilangan a dan b.


f(a, b) = a (if b == 0);
f(a, b) = f(b, a%b) otherwise

Ini merupakan algoritma klasik Euclid yang berjalan dalam O(log n) dengan n = min(a, b) — tergantung dengan detail implementasi, n = max(a, b) atau n = a+b juga memungkinkan.


Algoritma Euclid adalah contoh dari sebuah algoritma Divide and Conquer (D&C)


Karena kompleksitas yang rendah, tidak ada masalah untuk mencoba 0 ≤ a, b ≤ 99.
(kita mengacak nilai a dan b dalam rentang tersebut dan set a ≥ b).
Catat bahwa jika a < b, langkah rekursi pertama akan menukar a dan b.


Cobalah beberapa kombinasi dari a dan b dan perhatikan pada nilai berapakah f(a, b) berhenti dengan cepat dalam satu langkah (b = 0), dua langkah (b = gcd(a, b)), atau banyaknya langkah maksimum (cobalah ini) — untuk menunjukkan batasan bawah Ω(log n).

3-5. Jumlah Rentang Maksimum

Jumlah Rentang Maksimum menghitung nilai dari sublarik dengan jumlah nilai total maksimum dalam sebuah larik (global) a1 dengan n = a1.length bilangan (textbox pertama di bawah textbox editor kode). Nilai dari a1 bisa merupakan bilangan bulat positif, nol, atau negatif (tanpa bilangan negatif, jawabannya jelas merupakan jumlah dari semua bilangan dalam a1).


Secara formal, definisikan RSQ(i, j) = a1[i] + a1[i+1] + ... + a1[j], dengan 0 ≤ i ≤ j ≤ n-1 (RSQ adalah Range Sum Query). Max Range Sum (Jumlah Rentang Maksimum) ingin mencari optimal i dan j sehingga nilai RSQ(i, j) maksimum.


f(i) = max(ai[0], 0) (if i == 0, karena ai[0] bisa negatif);
f(i) = max(f(i-1) + ai[i], 0) otherwise

Kita memanggil f(n-1). Nilai terbesar dari f(i) merupakan jawabannya.


Inilah algoritma Kadane klasik yang berjalan dalam O(n).

3-6. Bilangan Catalan

Bilangan Catalan menghitung nilai dari Bilangan Catalan ke-n secara rekursif:


f(n) = 1 (if n == 0);
f(n) = f(n-1)*2*n*(2*n-1)/(n+1)/n; otherwise

Penjelasan ini adalah stub yang akan dikembangkan nantinya.

4. Contoh Rekursi - Dua Subsoal

Pada sub-bagian berikutnya, kita akan melihat contoh algoritma rekursif yang memiliki tepat dua sub-masalah, yaitu percabangan. Ukuran dari sub-masalah ini bisa identik atau bervariasi. Untuk contoh-contoh sub-masalah dua ini, pohon rekursi mereka biasanya akan jauh lebih besar dibandingkan dengan DAG rekursi mereka (terutama jika ada (banyak) sub-masalah yang tumpang tindih, yang ditunjukkan dengan simpul-simpul berwarna biru muda pada gambar pohon rekursi).


Saat ini, yang ditampilkan di layar adalah pohon rekursi dari hubungan Fibonacci.

4-1. Bilangan Fibonacci (Pohon)

Bilangan Fibonacci menghitung bilangan Fibonacci ke-n.


f(n) = n (if n <= 1); // yakni, 0 if n == 0 or 1 if n == 1
f(n) = f(n-1) + f(n-2) otherwise

Tidak seperti contoh Faktorial, kali ini, tiap rekursi mencabang menjadi dua subsoal lebih kecil (jika kita memanggil f(n-1) terlebih dahulu sebelum f(n-2), maka pohon rekursi di sisi kiri akan lebih tinggi daripada sisi kanan — cobalah menukar kedua subsoal).


Nilai dari Fibonacci f(n) bertumbuh sangat cepat dan pohon rekursinya — jika diimplementasikan sesuai dengan rekurens di atas — juga bertumbuh secara eksponensial, yakni, setidaknya Ω(2n/2), maka hanya coba untuk nilai kecil n ≤ 7 (untuk mencegah crash).


Pohon rekursi dari Fibonacci sering digunakan untuk menunjukkan ide dasar tentang rekursi, ketidak-efisiennya (karena banyak subsoal bertumpukan), dan hubungannya dengan topik Pemrograman Dinamis (DP).

4-2. Bilangan Fibonacci (DAG)

DAG Rekursi (ditampilkan di latar belakang) dari perhitungan Fibonacci hanya mengandung O(n) simpul dan dengan demikian dapat mencapai n yang lebih besar, yaitu n ≤ 30 (agar masih terlihat bagus dalam visualisasi ini; dalam praktiknya, n dapat mencapai jutaan dengan solusi DP ini).


Sebagian besar waktu, perhitungan Fibonacci ditulis dalam bentuk iteratif setelah seseorang memahami konsep DP.


Mungkin jarang berpikir dengan cara ini, tetapi visualisasi ini menunjukkan bahwa perhitungan Fibonacci f(n) pada dasarnya adalah menghitung jumlah jalur dari n ke simpul 1.

4-3. Koefisien Binomial C(n, k) (Pohon)

Contoh C(n, k) menghitung nilai koefisien binomial C(n, k).


f(n, k) = 1 (if k == 0); // 1 cara untuk ambil 0 dari n item
f(n, k) = 1 (if k == n); // 1 cara untuk ambil n dari n item
f(n, k) = f(n-1, k-1) + f(n-1, k) // ambil item terakhir atau diabaikan

Pohon rekursi dari C(n, k) bertumbuh sangat cepat, dengan pohon terbesar pada saat k = n/2, pohon lebih kecil pada saat k mendekati 0 atau n (beberapa jalur dengan daun pendek), dan pohon terpendek pada saat k adalah 0 atau n (hanya satu simpul).

4-4. Koefisien Binomial C(n, k) (DAG)

DAG rekursi dari C(n, k) sebenarnya merupakan Segitiga Pascal terbalik. Terdapat paling banyak O((n/2)*(n/2)) = O(n^2/4) simpul (saat k = n/2) walaupun secara praktik kita akan menggunakan sebuah tabel DP/memo dengan ukuran O(n^2). Maka, kita bisa menggunakan nilai lebih besar n ≤ 15 (agar terlihat bagus dalam visualisasi) dan k∈[0..n], termasuk k≈n/2.


TBC: Dalam masa dekat, kita mungkin menggambarkan sebuah simpul maya (0, 0) --- C(n, k) tidak akan sampai simpul tersebut kecuali jika kita mulai dari C(0, 0) dengan nilai 1 untuk memenuhi visualisasi Segitiga Pascal terbalik tersebut.

4-5. Knapsack 0-1 (Pohon)

Contoh Knapsack 0-1 menyelesaikan masalah Knapsack 0/1: Berapakah nilai maksimum yang kita dapat, jika diberikan sebuah tas yang bisa membawa beras maksimum w, dengan nilai dari item ke-i adalah a1[i], dan berat dari item ke-i adalah a2[i]?


Knapsack 0-1 mempunyai rekurens DP yang klasik f(i, w) yang kita panggil menggunakan f(n-1, max-w) dengan n = a1.length.


f(i, w) = f(i-1, w); // abaikan item i (selalu bisa)
f(i, w) = a1[i] + f(i-1, w-a2[i]); // ambil item i (if a2[i] <= w)
f(<0, w) = 0; // semua item telah ditentukan
f(i, 0) = 0; // tidak bisa mengambil item lainnya

Pohon rekursi dari rekurens DP ini mempunyai dikit (seperti contoh yang ditunjukkan sekarang) hingga banyak (cobalah semua item mempunyai berat yang sama, yakni satu) subsoal bertumpukan.

4-6. Knapsack 0-1 (DAG)

DAG rekursi dari Knapsack 0-1 hanya mempunyai O(n * max-w) simpul. Maka kita bisa menggunakan nilai lebih besar n ≤ 7 dan max-w ≤ 15 (agar tetap terlihat bagus dalam visualisasi ini).


Rekurens DP ini secara sederhana mencari jalur terpanjang (berbobot) dalam DAG implisit ini dan mempunyai kompleksitas waktu O(n * max-w).


Jika berat dari tiap item a2 bervariasi, DAG rekursi akan terlihat sedikit kosong. Coba set a2=[1,2,...,2^i] untuk sebuah DAG rekursi yang lebih padat (tetapi tidak ada tumpukan) atau a2=[1,1,...,1] (banyak tumpukan).

5. Contoh Rekursi - Subsoal Banyak

Pada sub-bagian berikutnya, kita akan melihat contoh algoritma rekursif yang memiliki banyak sub-masalah (1, 2, 3, ..., batas tertentu). Untuk banyak contoh ini, ukuran Pohon Rekursi mereka adalah eksponensial dan kita benar-benar perlu menggunakan Pemrograman Dinamis untuk menghitung DAG Rekursi mereka sebagai gantinya.

5-1. Subseq Menaik Terpanjang (DAG)

Contoh Subsekuens Menaik Terpanjang menyelesaikan masalah Longest Increasing Subsequence (LIS): Diberikan larik a1, berapa panjangkah Subsekuens Menaik Terpanjang dari a1?


DAG rekursi dari contoh default (tidak acak) adalah sebagai berikut: simpul j ∈ [0..i-1] ditatakan secara horizontal (dari kiri/simpul 0 ke kanan/simpul i-1), lalu diletakkan secara vertikal (sesuai dengan nilai a1[j]). Kita menggambarkan sebuah sisi antara j dan k jika a1[j] < a1[k] (dengan semua simpul mempunyai sebuah sisi tersembunyi menuju sebuah simpul maya dengan nilai max(a1)+1 pada sel kanan-atas sehingga semua LIS berakhir pada simpul maya tersebut dan kita bisa memulai rekursi f(i), i = a1.length-1). Maka, masalah LIS ini bisa divisualisasikan sebagai mencari jalur terpanjang pada DAG rekursi (implisit) ini.


Karena terdapat |V| = n simpul dan |E| = O(n^2) sisi (menggunakan kasus uji larik terurut seperti {1,2,4,8,16,...} untuk mendapatkan visualisasi bagus), kompleksitas waktu untuk menyelesaikan LIS menggunakan DP adalah O(n^2).


Sejak awal tahun 2000-an, kita seharusnya menggunakan solusi greedy+binary search yang lebih cepat dengan kompleksitas O(n log k) untuk LIS, tidak dijelaskan dalam slide ini.

5-2. Coin Change (Pohon)

Contoh Coin Change menyelesaikan masalah Coin Change: Diberikan daftar a1 yang terdiri dari nilai koin, berapa banyaknya koin minimum yang diperlukan untuk mendapatkan nilai tepat v?


Pohon rekursi dari contoh default (tidak diacak) memiliki v = 7 sen dan 4 koin yang dipilih secara khusus {4, 3, 1, 5}. Apa yang ditampilkan di layar adalah seluruh pohon rekursi dari fungsi Coin-Change rekursif.


Algoritma greedy tipikal untuk Coin-Change yang selalu mengambil nilai koin terbesar yang tidak melebihi nilai saat ini v akan terjebak pada cabang paling kanan: 7 sen (ambil koin 5 sen) → 2 sen (ambil koin 1 sen) → 1 sen (ambil koin 1 sen lagi) → 0 (total 3 koin).


Algoritma DP yang mengeksplorasi pohon rekursi ini (tetapi menghindari perhitungan berulang pada vertex berwarna biru muda) akan menemukan cabang paling kiri: 7 sen (ambil koin 4 sen) → 3 sen (ambil koin 3 sen) → 0 (total 2 koin). Solusi alternatif: 7 → 4 → 0 (juga 2 koin).

5-3. Memotong Tongkat (Pohon)

Contoh Memotong Tongkat menyelesaikan masalah 'fiksi' pengantar di Bab 14.1 - Pemrograman Dinamis dari buku teks "Introduction to Algorithms" (edisi ke-4 CLRS): Diberikan sebuah batang dengan panjang n inci dan tabel harga a1 untuk panjang 1,2,...,n inci, tentukan pendapatan maksimum yang dapat diperoleh dengan memotong batang dan menjual potongannya.

Pohon rekursi dari contoh default (tidak diacak) memiliki n = 4 inci. Yang ditampilkan di layar adalah seluruh pohon rekursi dari fungsi Cut-Rod.


f(n) = max(a1[i-1] + f(n-i)) ∀i∈[1..n];
f(0) = 0; // tidak bisa dipotong lagi

5-4. Perkalian Matriks (Pohon)

Contoh Matrix Chain Multiplication (MCM) menyelesaikan masalah pengantar DP kedua di Bab 14.2 dari buku teks "Introduction to Algorithms" (edisi ke-4 CLRS): Diberikan sebuah urutan (rantai) dari n = a1.length-1 matriks yang akan dikalikan, di mana matriks-matriks tersebut tidak harus berbentuk kuadrat, hitung hasil perkalian A1*A2*...*An menggunakan algoritma standar O(p*q*r) untuk mengalikan matriks persegi panjang, sambil meminimalkan jumlah perkalian skalar.

Pohon rekursi dari contoh default (tidak diacak) memiliki i=1,j=4. Yang ditampilkan di layar adalah seluruh pohon rekursi dari fungsi MCM.


f(i,j) = min(f(i,k)+f(k+1,j)+a1[i-1]*a1[k]*a1[j]) ∀i≤k<j;
f(i,j) = 0 if i == j; // no need to multiply a single matrix

5-5. Subseq Persekutuan Terpanjang (Pohon)

Contoh Subsekuens Persekutuan Terpanjang menyelesaikan masalah Longest Common Subsequence (LCS) : Diberikan dua string (larik karakter) a1 (dengan panjang n = a1.length) dan a2 (dengan panjang m = a2.length), berapa panjang Subsekuens Persekutuan Terpanjang dari kedua string tersebut?


f(n, m) = 1 + f(n-1, m-1); // if a1[n] == a2[m]; karakter terakhir cocok
f(n, m) = max(f(n-1, m), f(n, m-1)) // if karakter terakhir tidak cocok
f(n, <0) = 0; // a2 is empty
f(<0, m) = 0; // a1 is empty

Kita memanggil f(n-1, m-1), dari karakter terakhir kedua string.


Pohon rekursi dari rekurens DP ini mempunyai subsoal bertumpukan yang eksponensial (seperti yang saat ini ditunjukkan) jika kedua string mempunyai karakter berbeda yang banyak (namun cobalah juga a1 == a2; kita akan melihat sebuah pohon rekursi satu-subsoal).

5-6. Subseq Persekutuan Terpanjang (DAG)

DAG rekursi dari LCS hanya mempunyai O(n * m) simpul. Maka kita bisa menggunakan string lebih panjang dengan n ≤ 10 dan m ≤ 10 (agar tetap terlihat bagus dalam visualisasi).


DP rekurens ini secara sederhana mencoba mencari jalur (berbobot-0/1) terpanjang pada DAG implisit ini dan mempunyai kompleksitas waktu O(n * m).

5-7. Pencocokan Graf

Contoh Pencocokan Graf menghitung banyaknya matching maksimum pada graf kecil, yang diberikan dalam bentuk Adjacency Matrix a1.


Penjelasan ini adalah stub yang akan dikembangkan nantinya.

5-8. Traveling Salesperson Problem (TSP)

Contoh Traveling Salesperson menyelesaikan masalah Traveling Salesperson Problem untuk graf kecil: Berapa panjang dari jalur terpendek yang mulai dari kota 0, melalui tiap kota tepat sekali, dan kembali ke kota 0? Jarak dari kota i dan kota j dinyatakan sebagai a1[i][j].


Penjelasan ini adalah stub yang akan dikembangkan nantinya.

6. Contoh Rekurens D&C

Pada sub-bagian berikutnya, alih-alih memvisualisasikan pohon rekursi dari algoritma rekursif, kami memvisualisasikan pohon rekursi dari hubungan (persamaan) untuk membantu menganalisis kompleksitas waktu dari algoritma Divide and Conquer (D&C) tertentu.

Nilai yang dihitung oleh f(n) (label merah di bawah setiap simpul yang menunjukkan nilai kembalian dari fungsi rekursif/submasalah tersebut) adalah jumlah total operasi yang dilakukan oleh algoritma rekursif tersebut ketika ukuran masalahnya adalah n (nilai yang ditampilkan di dalam setiap simpul). Sebagian besar buku teks akan menyebut nama fungsi hubungan ini sebagai T(n), tetapi kami memilih untuk tidak mengubah nama fungsi default f(n) yang digunakan dalam semua visualisasi algoritma rekursif lainnya. Beberapa buku teks lainnya (misalnya, CLRS) juga hanya mencantumkan biaya dari setiap simpul saja, bukan biaya dari seluruh submasalah.

6-1. Analisis Merge Sort (1)

Pada visualisasi sorting, kita telah belajar tentang Merge Sort. Rekursi kompleksitas waktunya adalah:


f(n) = Θ(1) (if n < n0) —kita biasanya asumsi kasus dasarnya adalah Θ(1)
f(n) = f(n/2) + f(n/2) + c*n (selain itu)

Silahkan lihat pohon rekursi pada contoh default (n = 16). Kita akan emnggunakan pohon rekursi yang sama untuk beberapa sub-slide berikutnya. Anda dapat melihat ukuran masalah awal n = 16 tertulis dalam simpul akar dan nilainya (total pekerjaan yang dilakukan f(16) is 32+32+1*16 = 80). Nilai f(n) konsisten dalam pohon rekursi, seperti f(8) = f(4)+f(4)+1*4 = 12+12+1*8 = 32.

6-2. Analisis (2)

Kita bisa melihat bahwa ketinggian dari pohon rekursi ini adalah log2 n karena kita membagi n dengan 2 sampai kasus dasar dengan ukuran 1.

Untuk n = 16, kita punya 16-> 8-> 4-> 2-> 1 (log2 16 = 4 langkah).

Catatan: ketinggian pohon = banyaknya sisi dari akar ke daun terdalam.

6-3. Analisis (3)

Karena usaha yang dilakukan dalam langkah rekursif per submasalah ukuran n adalah c*n (operasi pembagian (trivial, Θ(1)) dan operasi penaklukan (penggabungan), Θ(n)), kita akan melakukan tepat cn operasi per setiap tingkat rekursi dari pohon rekursi spesifik ini.

Akar dengan ukuran (n) melakukan c*n operasi selama langkah penggabungan.

Dua anak dari akar dengan ukuran (n/2) masing-masing melakukan c*n/2, dan 2*c*n/2 = c*n juga.

Tingkat cucu adalah 4*c*n/4 = c*n juga.

Dan seterusnya hingga tingkat terakhir (daun).

Karena label merah di bawah setiap simpul dalam visualisasi ini melaporkan nilai seluruh submasalah (termasuk subpohon di bawahnya), biaya identik per tingkat tidak mudah terlihat, misalnya, dari akar ke daun, kita melihat 80, 2x32 = 64, 4x12 = 48, 8x4 = 32, 16x1 = 16 dan mungkin mendapatkan kesimpulan yang berbeda... Namun, jika kita mengurangi nilai dari submasalahnya, kita akan mendapatkan kesimpulan yang sama, misalnya, untuk akar, kita melakukan 80-2x32 = 16 operasi, untuk anak-anak akar, kita melakukan 2x(32-2x12) = 2x8 = 16 operasi juga, dan seterusnya.

Segera, kami akan menampilkan informasi 'kerja-yang-dilakukan-di-setiap-tingkat' secara langsung dalam visualisasi.

6-4. Analisis (4)

Banyaknya daun berwarna hijau adalah 2log2 n = nlog2 2 = n.


Setiap daun melakukan langkah Θ(1), maka total pekerjaan dari tingkat terakhir (daun) juga Θ(n).


Total pekerjaan yang dilakukan Merge Sort adalah c*n per tingkat, dikalikan dengan ketinggian dari pohon rekursi (log2 n + 1 lebih untuk tingkat daun), atau Θ(n log n).


Dalam contoh ini, f(16) = 80 dari 1x16 x (log2 16 + 1) = 16 x (4 + 1) = 16 x 5 = 80.

6-5. Analisis Quick Sort (Tak-Acak)

Pada visualisasi sorting, kita juga telah belajar tentang Quick Sort tanpa acakan.


Algoritma tersebut mempunyai kasus terjelek O(n2) dalam beberapa kasus (trivial) dan mempunyai rekursi waktu kompleksitas sebagai berikut (dengan a = 1):


f(n) = Θ(1) (if n < n0) — kita biasanya asumsi kasus dasarnya adalah Θ(1)
f(n) = f(n-a) + f(a) + c*n (otherwise)

Perhatikan bahwa menulis rekursi dalam arah sebaliknya tidak berpengaruh banyak, selain dari pohon rekursi menjadi terbalik.


Perhatikan pohon rekursi yang sekarang digambar.
Kita mau menunjukkan bahwa pohon rekursi ini mempunyai f(n) = O(n2).

6-6. Analisis (2)

Kita dapat melihat bahwa ketinggian dari pohon rekursi ini lumayan tinggi, yaitu n/a - 1 karena kita hanya mengurangi n dengan a pada setiap tingkat. Maka kita memerlukan n/a - 1 tingkat untuk sampai kasus dasar (n = 1).
Untuk n = 16, a = 1, kita punya 16-> 15-> 14-> ...-> 2-> 1 (16/1 - 1 = 15 langkah).

6-7. Analisis (3)

Karena pekerjaan yang dilakukan pada langka rekursi per subsoal untuk ukuran n adalah c*n (membagi (partisi) dalam Θ(n); bagian penaklukan mudah — Θ(1)), kita akan melakukan tepat c*n operasi per tingak rekursi.


Akar dengan ukuran (n) melakukan c*n operasi dalam tahap partisi.
Anak dari akar dengan ukuran (n-a) melakukan c*(n-1) dan lainnya melakukan f(a).
Tingkat cucu melakukan c*(n-2) operasi dan lainnya melakukan f(a).
Dan seterusnya sampai tingak terakhir (daun-daun melakukan f(a)).

6-8. Analisis (4)

Total pekerjaan yang dilakukan Quick sort pada kasus terburuk ini merupakan jumlah dari deret aritmetik 1+2+...+n ditambahkan operasi faktor konstan lainnya (semua f(a) adalah Θ(1)). Ini disederhanakan menjadi f(n) = Θ(n2).

6-9. Master Theorem, Kasus 1 (1)

Untuk rekurens dalam bentuk:

f(n) = a*f(n/b) + g(n)

dengan a ≥ 1, b > 1, dan g(n) adalah asimptotik positif,
kita bisa menggunkan master theorem (kadang juga disebut metode master).
Catatan: Dalam visualisasi ini, kita harus merubah nama fungsi CLRS menjadi konvensi kami:
f(n) → g(n) dan T(n) → f(n).


Kita bandingkan fungsi driving g(n) (banyaknya kerja yang dilakukan pada tiap langkah rekursi dengan ukuran n) dengan nlogba (fungsi watershed — juga merupakan banyaknya daun dari pohon rekursi secara asimptotik), jika g(n) = O(nlogba-ε) untuk ε > 0, maka fungsi driving g(n) bertumbuh lebih pelan secara polinomial daripada fungsi watershed nlogba (sebanyak faktor nε), maka fungsi watershed nlogba akan mendominasi dan solusi dari rekurensnya adalah f(n) = θ(nlogba).


Secara visual, jika anda melihat pohon rekursi untuk rekurens yang masuk dalam kategori kasus 1, total kerja per tingkat bertumbuh naik secara eksponensial dari tingkat akar ke tingkat daun (dalam gambar ini, 1*4*4 = 16, 7*2*2 = 28, 49*1*1 = 49, ..., 16+28+49 = 93), dan total kerja dari daun-daun mendominasi total kerja dari simpul-simpul internal lainnya.

6-10. Kasus 1 (2)

Contoh paling terkenal adalah algoritma Strassen untuk perkalian matriks dengan kasus 1 dari master theorem berlaku. Rekurensnya adalah: f(n) = 7*f(n/2) + c*n*n.


Maka a = 7, b = 2, watershed = nlog2 7 = n2.807, driving = g(n) = Θ(n2).


n2 = O(n2.807-ε) untuk ε = 0.807... — kasus 1 — Maka f(n) = Θ(n2.807)

Latihan: Anda bisa menggantikan kode demo dengan set a = 8 dan set g(n) = c*1 untuk merubah rekurens algoritma Strassen menjadi rekurens algoritma perkalian matriks sederhana yang mempunyai f(n) = Θ(n3).

6-11. Master Theorem, Kasus 2

Analisis mendalam algoritma Merge sort dari beberapa slide sebelumnya dapat disederhanakan menggunakan master theorem, yakni, f(n) = 2*f(n/2) + c*n.


Maka a = 2, b = 2, watershed = nlog2 2 = n, driving = g(n) = Θ(n).
n = Θ(n logk n) untuk k = 0
Fungsi watershed dan driving mempunyai pertumbuhan asimptotik yang sama — kasus 2
Maka f(n) = Θ(n log n).


Secara visual, jika anda melihat pohon rekursi untuk rekursi yang masuk dalam kategori kasus 2, total kerja per tingkat adalah ~sama, yakni Θ(nlogba logk n) dan terdapat logb n tingkat. Kita klaim bahwa solusinya adalah f(n) = Θ(nlogba logk+1 n). Itu saja, solusi dari rekursi yang masuk dalam kasus 2 adalah mengalikan sebuah faktor log tambahan pada g(n).


Latihan: Anda bisa menggantikan kode demo dengan set a = 1 dan set g(n) = c*1 untuk merubah rekurens Merge Sort menjadi rekurens pencarian biner (binary search). Untuk pencarian biner, f(n) = Θ(log n). Perhatikan untuk kebanyakan algoritma nyata kasus 2 (seperti Merge Sort dan Binary Search), k = 0.

6-12. Master Theorem, Kasus 3

Kasus 3 adalah kebalikan dari kasus 1, dengan fungsi driving g(n) bertumbuh lebih cepat secara polinomial dibandingkan fungsi watershed nlogba. Maka kebanyakan dari operasi akan dilakukan di fungsi driving pada tingkat akar (tetapi cek dengan kondisi regularity juga, akan dijelaskan di bawah). Kasus 3 jarang muncul dalam algoritma nyata, jadi kita akan menggunakan rekurens fiksi: f(n) = 4*f(n/2) + c*n^3.


Maka a = 4, b = 2, watershed = nlog2 4 = n2, driving = g(n) = Θ(n3).
n^3 = Ω(n2+ε) untuk ε = 1 dan
4*(n/2)3 ≤ c*n3 (kondisi regularity) untuk c = 1/2 — case 3
Maka f(n) = Θ(n3).


Secara visual, jika anda melihat pohon rekursi untuk rekurens yang masuk dalam kategori kasus 3, total kerja per tingkat menurun secara eksponensial dari tingkat akar ke tingkat daun (pada contoh gambar ini, 1*4*4*4 = 64, 4*2*2*2 = 32, 16*1*1*1 = 16, ..., 64+32+16 = 112), dan total kerja dari akar mendominasi total kerja dari semua simpul internal lainnya (termasuk daun-daun (yang banyak)).