J'ai vu une preuve pour trouver la complexité d'un algorithme de tri qui dit quelque chose comme ceci:
Total time complexity for the algorithm = T(n-1) + T(n-2)
Thus, Total time complexity for the algorithm <= 2 * T( n-2 )
et ensuite continué à prouver une relation.
Ques: Puis-je toujours supposer en toute sécurité que T(n) >= T(n-1) ? Quand j'essaie déjà de prouver la complexité d'un algorithme, comment puis-je faire cette affirmation avant de commencer?
Réponses:
6 pour la réponse № 1Non, vous ne pouvez pas faire une telle réclamation.
Considérons une fonction:
f(0) = 1000000! (factorial of 1000000)
f(n) = 1, for n>0
Ici, la complexité temporelle de la fonction avec le plus grand argument est plus petite que celle du bas.
Tout dépend des détails, en particulier - dans l'exemple fourni, vous avez déjà une déclaration
Total time complexity for the algorithm = T(n-1) + T(n-2)
ce qui équivaut à
T(n) = T(n-1) + T(n-2)
qui est une revendication forte sur la complexité, mais il ne semble pas juste de supposer
Thus, Total time complexity for the algorithm <= 2 * T( n-2 )
comme on peut en déduire
T(n) = T(n-1) + T(n-2)
cette
T(n) = T(n-1) + T(n-2) = (T(n-2) + T(n-3)) + T(n-2) >= 2 * T( n-2 )
Peut-être que la réclamation était-ce?
Thus, Total time complexity for the algorithm >= 2 * T( n-2 )
2 pour la réponse № 2
Non, vous ne pouvez pas toujours faire cette hypothèse, cela dépend de la fonction T.
Par exemple:
T(0) = T(1) = 1 //no important
T(2n) = T(2n-2) //all even numbers are calculated recursivel
T(2n+1) = 1 //all odd numbers
Ci-dessus, pour chaque n: T (n) <T (n-1)
Un exemple pratique où cela pourrait en fait être une fonction de complexité est si n doit être pair, et si ce n'est pas le cas, une erreur est renvoyée.
0 pour la réponse № 3
Non, cela dépend de l'algorithme.
Je pourrais définir un algorithme comme celui-ci: pour chaque entrée de taille n < 1000 essayer de faire quelque chose. si n > 1000 rendre une décision concluante.
Donc pour chaque n < 1000 il pourrait y avoir un calcul long et fatigant, mais pour n > 1000 ses O(1)
0 pour la réponse № 4
T(n) >= 2*T(n-2) est implicite, pour n>3, par la relation de récurrence T(n) = T(n-1)+T(n-2).
T(n-1) est T(n-2)+T(n-3).
Si T représente le coût d'un algorithme, il ne peut pas être négatif.
T(n-3) >= 0 implique T(n-1) >= T(n-2), et T(n) >= 2*T(n-2).
Ceci est juste une conséquence de la relation de récurrence spécifique, pas quelque chose que vous pouvez supposer en général, bien que cela soit vrai pour de nombreuses relations de récurrence qui apparaissent dans l'analyse par algorithme.