Memecahkan kekambuhan membagi & menaklukkan jika rasio split tergantung pada

20

Apakah ada metode umum untuk menyelesaikan pengulangan formulir:

T(n)=T(nnc)+T(nc)+f(n)

untuk , atau lebih umumc<1

T(n)=T(ng(n))+T(r(n))+f(n)

di mana adalah beberapa fungsi sub-linear dari .ng(n),r(n)n

Pembaruan : Saya telah melalui tautan yang disediakan di bawah ini dan juga menyaring semua hubungan perulangan dalam catatan Jeff Erickson . Bentuk perulangan ini tidak dibahas di mana pun. Metode Akkra-Bazi hanya berlaku ketika perpecahan fraksional Referensi yang pedih akan dinilai.

Plummer
sumber
2
Coba buat fungsi.
saadtaame
1
Apakah metode Akra-Bazzi berlaku? Ini hanya memberikan perkiraan O() , tetapi itu mungkin cukup.
vonbrand
4
Karena Anda tidak menyertakan banyak upaya untuk menyelesaikan masalah Anda sendiri, kami harus bekerja sama. Biarkan saya mengarahkan Anda ke pertanyaan referensi kami yang mencakup masalah yang mirip dengan Anda secara detail. Silakan bekerja melalui pertanyaan terkait yang tercantum di sana, cobalah untuk menyelesaikan masalah Anda lagi dan edit untuk memasukkan upaya Anda bersama dengan masalah spesifik yang Anda temui.
Raphael
1
Lihatlah handout Tom Leighton pada "Catatan tentang teorema master yang lebih baik untuk perulangan divide-and-conquer", mereka tersedia di internet. Mungkin Anda bisa menyesuaikan bukti Akra-Bazzi di sana untuk kasus Anda.
vonbrand
1
@EngrStudent Menghasilkan fungsi diusulkan di komentar pertama. :)
Raphael

Jawaban:

6

Katakanlah Anda memiliki kekambuhan bahwa rentang lebih real positif.

T(n)={T(n-nc)+T(nc)+f(n)n> 21jika tidak

Apa yang bisa kita lakukan dengan fungsi ini? Yah, tidak banyak kecuali kita menempatkan struktur tertentu di atasnya. Saya berasal dari latar belakang analisis numerik, yang diaspal dengan resep numerik yang entah bagaimana bekerja bahkan ketika masalah yang mendasarinya tidak cukup lancar (tidak masalah, mari kita masih membuang metode Newton pada perbedaan yang dibagi) atau terlalu rumit untuk dianalisis (sort seperti masalah ini). Reaksi saya terhadap masalah-masalah ini adalah membuat beberapa asumsi dengan tangan, menyilangkan jari, dan berharap yang terbaik. Dalam hal ini, tampaknya memberikan batas yang relatif bagus.

Secara khusus, saya ingin membuat dua asumsi utama. Salah satu asumsi ini kurang lebih tidak berdasar, tetapi kita tidak akan berhasil tanpa itu. Yang lain memiliki intuisi visual yang agak bagus yang mudah-mudahan Anda grok, tetapi masih jauh lebih tangan daripada yang lain.

  1. Saya akan menganggap bahwa adalah "smooth-ish". Cukup mudah untuk melihat bahwa T ( n ) tidak dapat dibedakan di semua tempat. Bahkan, itu bahkan tidak berkelanjutan, karena untuk f ( n ) = log ( n ) dan c = 1T(n)T(n)f(n)=catatan(n) ,limn2-T(n)=1danlimn2+T(n)=2+ln2. Oleh karena itu, mengingat peta iterasi yang dihasilkan olehnc=12limn2-T(n)=1limn2+T(n)=2+dalam2 ataunn-nn ,T(n)akan berisi diskontinuitas padanjika pohon itasinya berisi2tempat pada lintasannya. Itu adalah banyak diskontinuitas, bahkan mungkin membuat fungsi Dirichlet berjalan untuk mendapatkan uangnya. Jika kita sampai pada titik di mana kita membandingkan perilaku suatu fungsi dengan contoh prototipikal dari fungsi yang tidak berkesinambungan, tidakkah menggelikan untuk mencoba mengklaim bahwa itu "smooth-ish"? Nah, ternyata dalam prakteknya, efek diskontinuitas ini asimtotik berkurang, ke titik bahwa grafik penampilan Anda hampir halus saatnnn-nT(n)n2ncenderung menuju tak terbatas! Oleh karena itu, saya mengusulkan agar kita meletakkan garpu rumput dan melihat ke arah lain dalam keadaan ini. Secara khusus, saya akan berasumsi bahwa pada suatu titik yang menarik yang cukup jauh dari asal, T ( n ) dapat dibedakan, atau setidaknya kira-kira dapat dibedakan di sekitar beberapa lingkungan.nT(n)
  2. Saya juga akan mengasumsikan sikap kelancaran yang lebih kuat ketika cukup jauh. Misalkan α ( n ) adalah beberapa fungsi sublinear sehingga n > α ( n ) (misalnya n c ), maka turunan T ( ξ ( n - α ( n ) , n ) tidak bervariasi secara signifikan ketika α ( n ) cukup lambat, secara intuitif, seperti nnα(n)n>α(n)ncT(ξ(nα(n),n)α(n)nsemakin besar, ukuran relatif dari lingkungan berkurang (karena ukurannya hanya α ( n ) , yang tumbuh jauh lebih lambat daripada n ). Akhirnya, ukuran lingkungan ini menjadi sangat kecil (relatif terhadap n ) sehingga laju perubahan T ( n ) dalam lingkungan ini tidak lagi mengubah semua itu secara dramatis.(nα(n),n)α(n)nnT(n)

Sekarang, kedua properti ini diasumsikan, dan saya tidak punya ide bagaimana cara membuktikannya dengan cara yang keras. Tapi seperti yang saya katakan sebelumnya, mari kita menyilangkan jari dan berharap yang terbaik.

Mari kita mulai dengan hubungan perulangan: Sekarang, saya akan berasumsi bahwaTcukup halus pada interval antaran-ncdann. Menarik bagi salah satu alat analitik klasik kita, teorema nilai rata-rata, memberi kita T(n)-T(n- n c )

T(n)=T(nnc)+T(nc)+f(n)T(n)T(nnc)=T(nc)+f(n)ncT(n)T(nnc)nc=T(nc)+f(n)
Tnncn Lebih lanjut, ketikancukup besar, kita mengasumsikan bahwaT(ξ)kira-kira sama sepanjang interval ini, dan karenanya mengambil nilai dari setiap perbedaan hingga dalam interval ini juga. Ini berarti bahwa T(ξ)T(n)-T(n-ϵ)
T(n)T(nnc)nc=T(ξ(nnc,n)).
nT(ξ) Secara khusus, ambilϵ=1untuk mendapatkan pendekatan perbedaan satu langkah dibagi n c ( T ( n ) - T ( n - 1 ) )
T(ξ)T(n)T(nϵ)ϵ    ϵ<nc
ϵ=1 Kita bisa membuat teleskop ini untuk mendapatkan T(n)nkT(kc)
nc(T(n)T(n1))T(nc)+f(n)T(n)T(n1)T(nc)+f(n)nc
T(n)knT(kc)kc+knf(k)kc

Perturbing mengungkapkan bahwa T ( n ) memiliki dua fase asimptotik, tergantung pada sifat asimptotik dari f ( z ) .T(n)T(n)f(z)

f(n)=o(nc)fncT(n)=Θ(knf(k)kc)nf(x)xcdx

f(n)=ω(nc)

(knT(kc)kc)+Fc(n)
Fc(n)=nf(x)xcdx

nT(xc)xcdx

kT(kc)kcnf(xc)xcdx=nT(ξ<nc)ξc
nT(nc)nc
T(n)nMT(nc)nc+Fc(n)
M

(n,nc,nc2,nc3,,nck)nck<2

(*)T(n)n(ik1MinciFc(nci)+Mknck)
Once again, we can bound the Fc(nci) term by some constant to find that
T(n)=O(Fc(n)+nFc(nc)(Mnc+M2nc2++Mknck))
where k=logc(log(2)log(n)). Simplifying a bit and coalescing some of the Mnc terms together (in particular, we know that nck is a constant), we get
T(n)=O(nkFc(n)Mk)

However, this bound is relatively loose, and you should refer to (*) whenever possible.

Be aware that in no way is this rigorous. I have not provided any support that this ought to work beyond some clumsy approximations. Nevertheless, if you just need a quick asymptotic guess for the sake of informal analysis, then you can actually see that this scheme works well (for large enough values of n, usually n>10 suffices) in practice.

Anyways, for all of the choices of c and f that I've tried, the following computation

T^(n)=nklogclogn2MknckF(nck)F(n)=knf(k)kc
where
MkT(kc)kcnT(nc)nc
seems to give good approximations. This technique also generalizes to recurrences of the form
T(n)=T(nα(n))+T(β(n))+f(n)
which can be approximated with
T^(n)=nk#β(n)Mkαk(n)F(βk(n))F(n)=knf(k)α(k)
where αk(n)=α(k(α(n))) and #β(n) denotes the number of elements of the sequence n,β(n),β(β(n)),,β#β(n)(n) such that the last term is between 1 and 2.
Lee
sumber