Erreur dans l'utilisation de la notation asymptotique

J'essaie de comprendre ce qui ne va pas avec la preuve suivante de la récurrence suivante

T(n)≤2(c⌊

La documentation dit que c'est faux à cause de l'hypothèse inductive que Qu'est-ce que je manque?

Disons que le but final est de prouver . Vous commencez avec l'hypothèse d'induction:$T(n) = \mathcal{O}(n)$

pour tout i < n .$T(i) \leq ci$$i < n$

Et pour compléter la preuve, vous devez également montrer que .$T(n) \leq cn$

Cependant, ce que vous pouvez déduire est , ce qui n'est pas utile pour compléter la preuve; vous avez besoin d' une constante c pour (presque) tout n . Par conséquent, nous ne pouvons rien conclure et T ( n ) = O ( n ) n'est pas prouvé.$T(n) \leq (c+1)n$$c$$n$$T(n) = \mathcal{O}(n)$

Notez que vous êtes confus entre le résultat et le processus de preuve. Et encore un point, est en fait Θ ( n log n ) dans ce cas, vous pouvez donc considérer une hypothèse d'induction appropriée pour pouvoir le prouver.$T(n)$$\Theta(n \log n)$

Vous avez omis quelques étapes. Il semble que vous tentiez de prouver par induction que , et votre preuve va:$T(n) = O(n)$

Supposons que pour k < n . Cela signifie que T ( k ) ≤ $T(k) = O(k)$$k<n$ pour certains c . Alors T ( n ) = 2 T ( ⌊ n / 2 ⌋ ) + n ≤ 2 c ⌊ n / 2 ⌋ + n ≤ ( c + 1 $T(k) \le c \, k$$c$ , donc T ( n ) = O ( n ) .$T(n) = 2 T(\lfloor n/2\rfloor) + n \le 2 c \lfloor n/2\rfloor + n\le (c+1) \,n$$T(n) = O(n)$

Cette preuve va mal dès le départ: « pour k < n » n'a pas de sens. Big oh est une notion asymptotique: T ( k ) = O ( k ) signifie qu'il existe une constante c et un seuil N tels que ∀ k ≥ N , T ( k ) ≤ $T(k) = O(k)$$k \lt n$$T(k) = O(k)$$c$ . Et encore une fois à la fin, vous ne pouvez pas conclure que " T ( n ) = O ( n ) ", car cela dit quelque chose sur la fonction T dans son ensemble et vous avez seulement prouvé quelque chose sur la valeur particulière T ( n ) .$\forall k \ge N, T(k) \le c \, k$$T(n)=O(n)$$T$$T(n)$

Vous devez être explicite sur ce que signifie Alors peut-être que votre preuve va:$O$

Supposons que pour tout k < n . Alors T ( n ) = 2 T ( ⌊ n / 2 ⌋ ) + n ≤ 2 c ⌊ n / 2 ⌋ + n ≤ ( c + 1 $T(k) \le c \, k$$k < n$ .$T(n) = 2 T(\lfloor n/2\rfloor) + n \le 2 c \lfloor n/2\rfloor + n\le (c+1) \,n$

Cela ne prouve pas une étape inductive: vous êtes parti de , et vous avez prouvé que pour k = n , T ( k ) ≤ ( c + 1 $T(k) \le c \, k$$k=n$ . C'est une limite plus faible. Regardez ce que cela signifie: T ( k ) ≤ $T(k) \le (c+1) \, k$ signifie que c est une borne pour le taux de croissance de T . Mais vous avez un taux c qui augmente lorsque k augmente. Ce n'est pas une croissance linéaire!$T(k) \le c \, k$$c$$T$$c$$k$

Si vous regardez attentivement, vous remarquerez que le taux augmente de 1 chaque fois que k double. Donc, de manière informelle, si m = 2 p k alors c m = c k + p ; en d'autres termes, c k = c 0 log 2 k .$c$$1$$k$$m=2^p k$$c_m = c_k + p$$c_k = c_0 \log_{2} k$

Cela peut être précisé. Démontrer par induction que pour , T ( k ) ≤ c log 2 ( k ) .$k \ge 1$$T(k) \le c \log_2(k)$

La relation de récurrence est typique des algorithmes de division et de conquête qui divisent les données en deux parties égales en temps linéaire. De tels algorithmes opèrent dans temps (pas O ( n ) ).$\Theta(n\,\mathrm{log}(n))$$O(n)$

Pour voir quel est le résultat attendu, vous pouvez vérifier la relation de récurrence par rapport au théorème maître . La division est et le travail supplémentaire effectué est n ; log 2 ( 2 ) = 1 c'est donc le deuxième cas pour lequel la croissance est Θ ( $2T(n/2)$$n$$\log_2(2) = 1$ .$\Theta(n\,\log(n))$

J'étends la réponse déjà donnée, peut-être seulement en expliquant mon commentaire plus en détail.

Comme deviner peut clairement être difficile et fastidieux, il existe parfois de meilleures méthodes. L'une de ces méthodes est le théorème maître . Notre récurrence est maintenant de la forme , où a ≥ 1 et b > 1 sont des constantes et f ( n ) une fonction. Notez que dans notre cas, ⌊ n / 2 ⌋ peut être interprété comme signifiant n /$T(n) = a T(n/b) + f(n)$$a \geq 1$$b > 1$$f(n)$$\lfloor n/2 \rfloor$$n/2$. Pour être techniquement exact, notre récurrence peut ne pas être bien définie car peut ne pas être un entier. Cependant, cela est autorisé car cela n'affectera pas le comportement asymptotique de la récidive. Par conséquent, nous trouvons souvent pratique de laisser tomber les planchers et les plafonds. La preuve formelle de cela est un peu fastidieuse, mais le lecteur intéressé peut la trouver par exemple dans Cormen et al. livre .$n/2$

Dans notre cas, nous avons , b = 2 , f ( n ) = Θ ( n ) . Cela signifie que nous avons n log b a = n log 2 2 = n . Le deuxième cas du théorème maître s'applique puisque f ( n ) = Θ ( n ) , et nous avons la solution T ( n ) = Θ ( n $a = 2$$b = 2$$f(n) = \Theta(n)$$n^{\log_b a} = n^{\log_2 2} = n$$f(n) = \Theta (n)$ .$T(n) = \Theta (n \log n)$