Perkiraan asimtotik dari hubungan perulangan (Akra-Bazzi tampaknya tidak berlaku)

10

Misalkan suatu algoritma memiliki hubungan pengulangan runtime:

T(n)={g(n)+T(n1)+T(δn):nn0f(n):n<n0

untuk beberapa konstanta . Asumsikan adalah polinomial dalam , mungkin kuadratik. Kemungkinan besar, akan eksponensial dalam .0<δ<1gnfn

Bagaimana cara menganalisis runtime ( akan sangat baik)? Teorema master dan metode Akra-Bazzi yang lebih umum tampaknya tidak berlaku.Θ

Austin Buchanan
sumber
Menemukan batas bawah yang baik itu mudah tetapi menemukan batas atas yang baik itu sulit, tetapi berbicara kasar sepertinya dekat dengan . T(n)=aT(n/a)+g(n)
1
Jika Anda masih mencari jawaban, Anda harus memeriksa Graham, Knuth, dan Patashnik, "Matematika Beton".
Kaveh
Dengan asumsi bahwa adalah konstan, kita tidak memerlukan asumsi apa pun pada , atau bukan? n0f
Raphael
Parameter mungkin spesifik-instance. Akan menyenangkan untuk melihat bagaimana runtime tergantung pada . n0n0
Austin Buchanan
1
Saya mengajukan pertanyaan terkait yang, sejauh ini, belum menghasilkan teorema umum untuk pengulangan seperti ini.
Raphael

Jawaban:

5

Salah satu pendekatan yang mungkin adalah dengan analogi dengan persamaan diferensial. Misalkan . Di sini adalah analog diskrit dari turunan pertama . Kami mendapatkan hubungan berikut: Analog kontinu dari ini adalah persamaan diferensial atau, jika Anda lebih suka melihatnya ditulis secara berbeda: Itu persamaan diferensial.T(n)=T(n)T(n1)T(n)T(n)

T(n)=T(δn)+g(n).
t(x)=t(δx)+g(x),
ddxt(x)=t(δx)+g(x).

Sekarang Anda bisa mencoba menyelesaikan persamaan diferensial untuk fungsi kontinu , kemudian berhipotesis bahwa fungsi yang sama akan menjadi solusi untuk relasi perulangan asli Anda, dan coba buktikan hipotesis Anda. Setidaknya, ini adalah salah satu pendekatan umum yang bisa Anda ikuti.t(x)

Saya sudah lupa semua yang pernah saya ketahui tentang persamaan diferensial, jadi saya tidak tahu solusi persamaan diferensial itu, tetapi mungkin Anda akan dapat menyelesaikannya dengan meninjau semua teknik untuk menyelesaikan persamaan diferensial.

DW
sumber
Donald J Newman tampaknya telah sering menggunakan teknik ini, dengan hasil yang luar biasa.
Aryabhata
Tanpa melihat lebih jauh. Tidak mudah untuk menyelesaikan persamaan diferensial itu. Saya tidak terlalu yakin bahwa ia memiliki solusi bentuk tertutup setelah mencoba beberapa bentuk dasar untuk . t(x)
InformedA