Les questions: alt text http://img12.imageshack.us/img12/2706/image2ot.jpganalyse de l'algorithme Big-O
Qu'est-ce que je l'ai fait: alt text http://img29.imageshack.us/img29/9192/image3sc.jpg
Mais j'ai totalement aucune idée de la différence entre 3,5 et 3,6.
Si vous êtes un peu plus prudent dans votre solution à 3.5, la différence sera un peu plus claire. Votre première ligne
T(n) <= n/4 (lg n)/4 + 3n/4 (3 lg n)/4 + n
n'est pas tout à fait raison. Tout d'abord, l'hypothèse inductive est qu'il existe une constante C telle que
T(n) <= C n log n
donc vous devriez probablement garder cette C autour. Deuxièmement, vous sautez l'étape où vous supprimez la fonction de plancher. Ce que vous vraiment savoir est (en ignorant le C constant de simplicité) est
T(n) <= floor(n/4) lg (floor(n/4)) + floor(3n/4) lg (floor(3n/4)) + n
Alors, comment voulez-vous prendre soin du plancher? Eh bien, floor(x) <= x; mais qu'en est-il lg(floor(x)) (qui apparaît deux fois)? La clé ici est que lg est une fonction croissante, donc lg(floor(x)) <= lg(x) aussi. Alors
T(n) <= n/4 lg(n/4) + 3n/4 lg(3n/4) + n
nettoyer Maintenant avec quelques propriétés de logarithmes (vous sera besoin d'utiliser cette indication sur lg 3) et terminer votre étape inductive. OK, donc sachant cela, quelle est la différence avec 3.6? Eh bien, maintenant vous avez la fonction de plafond au lieu de la fonction de plancher, donc vous ne pouvez pas l'ignorer. Mais
ceiling(x) <= x + 1
afin que vous puissiez travailler de même, certains facteurs + 1 supplémentaires qui traînent. Essayez d'utiliser leurs conseils, et ça devrait aller.
La différence entre 3.5 et 3.6 est les fonctions de plafond et de plancher dans T (n/4). À part ça, ils sont identiques. Et autant que je peux dire que la différence n'a pas d'importance pour les calculs de O (T (n)) comme vous pouvez le voir à partir des résultats attendus.
J'espère que cela aide.
Je ne pense pas que ça aide. Notez que le texte en 3.6 affirme que l'exercice est difficile, donc quelque chose doit avoir de l'importance ici. –
La différence sera vraisemblablement de montrer à quelle vitesse la série converge. Mais à part ça, l'attaque devrait être la même. – dmckee
@dmckee: O (n log n) ne concerne pas la convergence. Par exemple, le péché (x) est dans O (1), mais le péché ne convergera jamais. –
Bonne réponse. C'est autant de soutien que nous pouvons donner. –
Merci. J'essayais de montrer les points clés, mais laissez les détails pour l'affiche. Si vous pensez que je devrais donner plus ou moins de détails, s'il vous plaît faites le moi savoir. –