Mengubah variabel dalam hubungan pengulangan

Saat ini, saya mempelajari sendiri Intro to Algorithms (CLRS) dan ada satu metode khusus yang mereka uraikan dalam buku ini untuk menyelesaikan hubungan perulangan.

Metode berikut dapat diilustrasikan dengan contoh ini. Misalkan kita mengalami kekambuhan

T (n) = 2 T (\sqrt{n}) + \log n

$T(n) = 2T(\sqrt n) + \log n$

Awalnya mereka membuat substitusi m = lg (n), dan kemudian hubungkan kembali ke perulangan dan dapatkan:

T (2^{m}) = 2 T (2^{\frac{m}{2}}) + m

$T(2^m) = 2T(2^{\frac{m}{2}}) + m$

Sampai pada titik ini saya mengerti dengan sempurna. Langkah selanjutnya ini yang membingungkan saya.

Mereka sekarang "mengubah nama" pengulangan dan membiarkan , yang tampaknya menghasilkan $S(m)$ $S(m) = T(2^m)$

S (m) = 2 S (m / 2) + m

$S(m) = 2S(m/2) + m$

Untuk beberapa alasan tidak jelas bagi saya mengapa penggantian nama ini berhasil, dan sepertinya curang. Adakah yang bisa menjelaskan ini dengan lebih baik?

asymptotics recurrence-relation mathematical-analysis landau-notation goooser
sumber

Jawaban:

Ini tentu saja tidak curang. Pikirkan dalam kalkulus bagaimana substitusi dapat digunakan untuk memecahkan integral yang rumit. Substitusi membuat persamaan lebih mudah dikelola untuk manipulasi. Selain itu, substitusi dapat mengubah rekurensi yang agak rumit menjadi yang biasa.

Inilah yang terjadi dalam contoh Anda. Kami mendefinisikan pengulangan baru . Ingat bahwa . Perhatikan bahwa, . Jika titik khusus ini masih belum jelas, misalkan dan perhatikan semua yang kita lakukan adalah . Sekarang, kita dapat mengekspresikan dengan memperluasnya ke: Memecahkan untuk kita melihat bahwa itu diselesaikan ke teman akrab . Sekarang kita telah menyelesaikan kita ingin mengekspresikan ini dalam bentuk . Untuk melakukan ini, cukup tancapkan kembali nilai asli kami untuk $S(m)=T(2^m)$ $T(2^m) = 2T(2^\frac{m}{2}) + m$ $S(m/2) = T(2^\frac{m}{2})$ $k =m/2$ $S(k) = T(2^k)$ $S(m)$

S (m) = 2 S (m / 2) + m .

$S(m) = 2S(m/2) + m.$

S

$S$

O (m \log m)

$O(m \log m)$

S

$S$

T (n)

$T(n)$

m

$m$ dan kami memiliki .

T \in O (\log n \log \log n)

$T \in O(\log n \log \log n)$

Nicholas Mancuso
sumber

Benar, saya benar-benar mengerti bagaimana penggantian membantu membuat masalah lebih mudah dan bagaimana memasukkan nilai kembali untuk mendapatkan kompleksitas dalam hal n. Saya kira pertanyaan saya adalah, setelah membiarkan S (m) = T (2 ^ m), bagaimana Anda menurunkan S (m / 2)? Tidak jelas bagi saya untuk beberapa alasan. Untuk lebih spesifik, bagaimana Anda menyimpulkan bahwa T (2 ^ (m / 2)) = S (m / 2). Sepertinya dalam rekurensi T, ukuran subproblem sedang berakar persegi, sedangkan dalam perulangan S, ukuran subproblem sedang dibelah dua

Satu-satunya bagian yang saya tidak mengerti adalah ketika Anda mengatakan "Perhatikan itu, S (m / 2) = T (2 ^ (m / 2))" Itulah satu-satunya bagian yang tidak jelas bagi saya. Saya sudah terbiasa dengan ide membuat substitusi variabel, tapi saya tidak benar-benar terbiasa dengan ide untuk mengganti seluruh pengulangan.

Ah ok, suntingan terakhir itu melakukannya untuk saya. Sudah jelas sekarang, terima kasih!

Saya sedikit ragu. Jika saya menulis fungsi S () dalam hal ksaya mendapatkan bawah persamaan S (k) = 2S (k / 2) + m Bagaimana saya bisa mendapatkan pengganti muntukk

Atinesh

Yang dimaksud adalah bahwa dan adalah dua fungsi berbeda yang menghasilkan hasil yang sama sambil mengambil input masing-masing sebagai dan . $S(m) = T(2^m)$ $S$ $T$ $m$ $2^m$

Fungsi dapat dianggap sebagai operator dengan dua langkah internal (jika tidak, komposisi fungsi): $S$

$S'$ : Input: , Output: $m$ $2^m$
$T$ Operator (fungsi asli): Input: output dari bagian pertama, Output: Seperti yang didefinisikan pada awalnya.

Maka transisi adalah:

m \to 2^{m} \to T (2^{m}) = S (m)

$m\to 2^m\to T(2^m) = S(m)$

\frac{m}{2} \to 2^{m / 2} \to T (2^{m / 2}) = S (\frac{m}{2}) .

$\tfrac{m}2\to2^{m/2}\to T(2^{m/2}) = S(\tfrac{m}2)\,.$

Vivek Anand Sampath
sumber