Maître du théorème avec f(n)=log n

Pour maître le théorème de T(n) = a*T(n/b) + f(n) je suis à l'aide de 3 cas:

  1. Si a*f(n/b) = c*f(n) pour certains constante c > 1 puis T(n) = (n^log(b) a)
  2. Si a*f(n/b) = f(n) puis T(n) = (f(n) log(b) n)
  3. Si a*f(n/b) = c*f(n) pour certains constante c < 1 puis T(n) = (f(n))

Mais quand f(n) = log n ou n*log n, la valeur de c dépend de la valeur de n. Comment puis-je résoudre la fonction récursive à l'aide de maître du théorème?

OriginalL'auteur amir shadaab | 2013-03-31

  1. 2

    Vous pourriez trouver ces trois cas de l'article de Wikipedia sur le Maître théorème un peu plus utile:

    • Cas 1: f(n) = Θ(nc), où c < logb un
    • Cas 2: f(n) = Θ(nck n), où c = logb un
    • Cas 3: f(n) = Θ(nc), où c > logb un

    Maintenant il n'y a pas de dépendance directe sur le choix de n plus - tout ce qui compte, c'est le long terme taux de croissance de f et comment il se rapporte à l'une des constantes a et b. Sans voir plus de détails sur le particulier récurrence que vous essayez de résoudre, je ne peux plus offrir des conseils spécifiques.

    Espérons que cette aide!

    Donc, pour un cas où f(n) = log n et un!=b, elle ne rentre pas 2e cas comme le c et k devrait être 1, mais il va me donner la fonction n*log n. Alors, comment puis-je vérifier où cette fonction correspond? Désolé pour toutes les questions.
    Notez que log n est pas Theta(n^c) pour toute constante c. Le seul cas possible qui travaille ici est celui du milieu, qui pourrait fonctionner si vous aviez que a = b. Si a != b, alors vous ne pouvez pas appliquer directement le Maître de pythagore pour résoudre la récurrence et devra trouver une autre approche.
    C'est exactement ce que je voulais entendre! Merci beaucoup!
    Mais, comment puis-je résoudre la fonction si f(n) = log(n)? Je suis confus
    Le maître théorème ne peut pas toujours être appliquée. Si cela ne fonctionne pas, vous devez utiliser une approche différente. Quelles sont précisément les récidives sont que vous essayez-vous de résoudre?

    OriginalL'auteur templatetypedef

  2. 7

    Habituellement, f(n) doit être polynôme pour le maître du théorème s'applique - elle ne s'applique pas pour toutes les fonctions. Cependant, il y a un "quatrième cas" pour le maître théorème, qui lui permet d'appliquer à polylogarithmic fonctions.

    Si f(n) = O(nbak n), puis T(n) = O(nba k+1 n).

    En d'autres termes, supposons que vous avez T(n) = 2T (n/2) + n log n. f(n) n'est pas un polynôme, mais f(n)=n log n, et k = 1. Par conséquent, T(n) = O(n log2 n)

    Voir ce document pour plus d'informations: http://cse.unl.edu/~choueiry/S06-235/fichiers/MasterTheorem-HandoutNoNotes.pdf

    OriginalL'auteur user3814579