Preuve Big-O pour une relation de récurrence?

Cette question est assez spécifique dans la manière de prendre les mesures pour résoudre le problème.

Donné $T(n)=2T(2n/3)+O(n)$ prouve-le $T(n)=O(n^2)$ .

Les étapes étaient donc les suivantes. Nous voulons prouver que $T(n) \le cn^2$ .

\begin{aligned} T (n) & = 2 T (2 n / 3) + O (n) \\ \leq 2 c (2 n / 3)^{2} + une n \\ \leq (8 / 9) (c n^{2}) + une 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*}$ puis mon prof a continué à faire:

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

$T(n) \leq cn^2+(an-(1/9)cn^2)\,,$ ce qui revient à:

T (n) \leq c n^{2} pour toute c > = 9 une .

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

Ma question est, comment ont-ils pu passer du 8/9 au 1/9 tout en introduisant un nouveau terme? Est-ce permis? Elle n'a jamais expliqué, c'était juste dans ses solutions.

asymptotics recurrence-relation D. Johnson
la source

Je ne vois pas de nouveau terme introduit? Nous avons ça

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

$cn^2 +an - (1/9)cn^2$ simplifie à

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

$(8/9)cn^2 + an$ comme dans la ligne précédente. Donc, les deux lignes sont en fait égales. Peut-être vous demandez-vous pourquoi on pourrait vouloir faire cela?

user340082710

Je suppose également que la dernière ligne doit se lire

c n^{2}

$cn^2$ par opposition à

c k^{2}

$ck^2$ .

user340082710

@ZacharyFrenette Ah tu as raison. dans ce cas, je ne savais pas trop comment elle avait fait la simplification. Pourquoi choisirait-on de séparer les termes de cette façon? il existe de nombreuses façons de diviser (8/9). Je pense que je sais pourquoi on voudrait faire ça, annuler ce supplément

a n

$an$ ? Sinon, l'inégalité ne tiendra pas. Merci aussi d'avoir souligné la faute de frappe, cela va corriger. si vous souhaitez commenter comme réponse, je peux l'accepter.

D. Johnson

Preuve Big-O pour une relation de récurrence?

Réponses: