Je lis "Analyse des algorithmes" par Sedgewick et Flajolet.In la page 7 Theoren 1.1 donne:comparaison de tri fusion
Et la preuve est donnée ci-dessous: 
certains peuvent expliquer ceci où O (N) va? Parce qu'il prouve que Cn est O (NlogN).
Vous avez raison; Pour des raisons qui me dépassent, ils ont déclaré plus de théorèmes qu'ils ne l'ont prouvé. Voici une façon de remplir le reste.
Lemme Soit T (n) pour les nombres entiers n> = 1 être défini par
T(n) = 0, for n = 1;
T(floor(n/2)) + T(ceil(n/2)) + n, for n > 1.
Alors T (n) < = n lg n + n - 1 = n lg n + O (n) pour les entiers n> = 1.
Preuve Par induction. Pour n = 1, T (1) = 0 = 1 lg 1 + 1 - 1. Pour n> 1, il y a deux cas. Si n est pair, alors
T(n) = 2T(n/2) + n
<= 2(n/2) lg(n/2) + 2n/2 - 2 + n
= n (lg n - 1) + 2n - 2
< n lg n + n - 1.
Si n est impair, alors les choses se compliquent.
T(n) = T(n/2 - 1/2) + T(n/2 + 1/2) + n
<= (n/2 - 1/2) lg(n/2 - 1/2) + (n/2 - 1/2) - 1
+ (n/2 + 1/2) lg(n/2 + 1/2) + (n/2 + 1/2) - 1
+ n
= (n/2 - 1/2) lg(n/2 - 1/2) + (n/2 + 1/2) lg(n/2 + 1/2) + 2n - 2.
Les deux termes laids deux sont proches de (n/2) lg (n/2), de sorte que nous écrivons chacun tels que quantité plus un terme d'erreur.
T(n) <= (n/2 - 1/2) lg(n/2 - 1/2) + (n/2 + 1/2) lg(n/2 + 1/2) + 2n - 2
= (n/2) lg(n/2) + ((n/2 - 1/2) lg(n/2 - 1/2) - (n/2) lg(n/2))
+ (n/2) lg(n/2) + ((n/2 + 1/2) lg(n/2 + 1/2) - (n/2) lg(n/2))
+ 2n - 2
= n lg(n/2) + 2n - 2
+ (n/2 - 1/2) lg(n/2 - 1/2) - (n/2) lg(n/2)
+ (n/2 + 1/2) lg(n/2 + 1/2) - (n/2) lg(n/2)
= n (lg n - 1) + 2n - 2
+ (n/2) (lg(n/2 - 1/2) - lg(n/2)) - (1/2) lg(n/2 - 1/2)
+ (n/2) (lg(n/2 + 1/2) - lg(n/2)) + (1/2) lg(n/2 + 1/2)
= n lg n + n - 2
+ (n/2) lg((n/2 - 1/2)/(n/2)) - (1/2) lg(n/2 - 1/2)
+ (n/2) lg((n/2 + 1/2)/(n/2)) + (1/2) lg(n/2 + 1/2)
= n lg n + n - 2
+ (n/2) lg(1 - 1/n) - (1/2) lg(n/2 - 1/2)
+ (n/2) lg(1 + 1/n) + (1/2) lg(n/2 + 1/2)
= n lg n + n - 2
+ (n/2) lg(1 - 1/n) + (n/2) lg(1 + 1/n)
+ (1/2) lg(n/2 + 1/2) - (1/2) lg(n/2 - 1/2)
= n lg n + n - 2
+ (n/2) lg((1 - 1/n) (1 + 1/n))
+ (1/2) lg((n/2 + 1/2)/(n/2 - 1/2))
= n lg n + n - 2
+ (n/2) lg(1 - 1/n^2)
+ (1/2) lg(1 + 2/(n - 1)).
Le terme (n/2) lg (1 - 1/n^2) est négative, et, pour n> = 3, le minimum n pour ce cas, l'expression (2.1) lg (1 + 2/(n - 1)) est au plus 1/2. (En fait, nous pourrions revenir en arrière et refaire la preuve pour montrer que T (n) < = n lg n + n/2 - 1/2, je vais laisser cela comme un exercice.) Par conséquent,
T(n) < n lg n + n - 2
+ 0
+ 1
= n lg n + n - 1.
beaucoup de mercis. – amitabha
Je ne sais pas exactement où le O (N) que vous demandez est erroné ou manquant, mais leur analyse est très bien pour le cas particulier N = 2^n.
La première ligne de maths après (1) ré-indique juste la récurrence pour le cas spécial. La prochaine, longue lignée de mathématiques montre
C_{2^n} = (2^n) n
Maintenant, nous savons 2^n = N et ainsi n = lg N. En substituant avec ces deux, on obtient
C_N = N lg N
comme on dit. Si je ne vois pas votre question correctement, veuillez commenter.
Sans avoir fait une analyse rigoureuse, je crois que le terme O (N) est nécessaire lorsque N ≠ 2^n. Dans ce cas, le nombre de comparaisons est C_N + R, où R est le nombre des comparaisons restantes, qui sont la différence entre N et le 2^n immédiatement inférieur, et donc bornées par O (N) (en fait, 0
Il est important de faire la distinction entre les formules exactes et les limites asymptotiques. Le O (N) doit être indiqué dans la formule par ailleurs "N lg N + O (N)". Il peut être supprimé lorsque seule la limite O (N lg N) est indiquée. –
Cette question semble être hors-sujet car il s'agit de maths – mishik