Bukti Big-O untuk relasi berulang?

Pertanyaan ini cukup spesifik dalam cara langkah-langkah yang diambil untuk menyelesaikan masalah.

Diberikan membuktikan bahwa . $T(n)=2T(2n/3)+O(n)$ $T(n)=O(n^2)$

Jadi langkah-langkahnya adalah sebagai berikut. Kami ingin membuktikan itu $T(n) \le cn^2$ .

\begin{aligned} T (n) & = 2 T (2 n / 3) + O (n) \\ \leq 2 c (2 n / 3)^{2} + a n \\ \leq (8 / 9) (c n^{2}) + a n \end{aligned}

$\begin{align*} T(n)&=2T(2n/3)+O(n) \\ &\leq 2c(2n/3)^2+an\\ &\leq (8/9)(cn^2)+an \end{align*}$ dan kemudian prof saya melanjutkan:

T (n) \leq c n^{2} + (a n - (1 / 9) c n^{2}),

$T(n) \leq cn^2+(an-(1/9)cn^2)\,,$ yang keluar ke:

T (n) \leq c n^{2} for any c >= 9 a .

$T(n)\leq cn^2 \text{ for any }c >= 9a\,.$

Pertanyaan saya adalah, bagaimana mereka bisa beralih dari 8/9 ke 1/9 saat memperkenalkan istilah baru? Apakah ini diizinkan? Dia tidak pernah menjelaskan, ini hanya dalam solusinya.

asymptotics recurrence-relation D. Johnson
sumber

Saya tidak melihat istilah baru diperkenalkan? Kami memilikinya

c n^{2} + a n - (1 / 9) c n^{2}

$cn^2 +an - (1/9)cn^2$ disederhanakan menjadi

(8 / 9) c n^{2} + a n

$(8/9)cn^2 + an$ seperti pada baris sebelumnya. Jadi kedua garis itu sebenarnya sama. Mungkin Anda bertanya mengapa orang ingin melakukan ini?

user340082710

Saya juga berasumsi bahwa baris terakhir harus dibaca

c n^{2}

$cn^2$ sebagai lawan

c k^{2}

$ck^2$ .

user340082710

@ZacharyFrenette Ah Anda benar. dalam hal ini, saya tidak yakin bagaimana dia melakukan penyederhanaan. Mengapa orang memilih untuk memisahkan persyaratan dengan cara itu? ada banyak cara untuk membagi (8/9). Saya pikir tahu mengapa seseorang ingin melakukan ini, untuk membatalkan tambahan itu

a n

$an$ ? Kalau tidak, ketidaksetaraan tidak akan berlaku. Juga terima kasih telah menunjukkan kesalahan ketik, akan diperbaiki. jika Anda ingin berkomentar sebagai jawaban, saya dapat menerimanya.

D. Johnson

Bukti Big-O untuk relasi berulang?

Jawaban: