J'ai visionnez des conférences vidéo sur le site OpenCourseWare du MIT, et la troisième lecture vidéo conférencier va plus récursive Multiplication de matrice et vient avec la complexité du temps être:Méthode du maître, quel cas?
T(n) = Θ(n3)
Il est évident pour moi que j'ai vraiment besoin de revoir certaines de mes maths, mais je ne vois vraiment pas le lien entre cette réponse et n'importe lequel des cas mentionnés pour la méthode du théorème du maître. Je sais que la relation récursive est de la forme:
T(n) = a*T(n/b) + f(n) pour n> 1.
Avec cette relation récursive: a = 8, b = 2 et f(n) = Θ(n2).
Alors, comment ont-ils obtenu Θ(n3)?
Il a mentionné que log28 = 3, ce qui est logique. Mais, je ne peux juste pas savoir lequel des trois cas que l'exemple de relation récursive correspond à, en utilisant la valeur de f(n).
Depuis, le cas 2 est le seul où f(n) = Θ(anything), alors je devine que c'est tout. Pourtant, je suppose que mon problème concerne les propriétés des logarithmes ou des exposants.
Si f(n) = Θ(nlog28 * (log2n)k+1) alors comment passer de Θ(n3) pour f(n) à Θ(n2) en utilisant le cas 2? Qu'est-ce que je pourrais manquer ici?
Merci. Avant de lire votre réponse, j'ai laissé la vidéo jouer et j'ai trouvé que c'était le cas 1. Similaire à votre réponse, je me suis dit qu'ils sont toujours dans le grand Omicron parce qu'il a f (n) <= c * g (n) condition pour f (n) = O (n). Donc, puisque Theta (n) implique que f (n) = c * g (n), alors il reste dans O (n). –