Exercice en mathématiques
Exercice 1 : Généralités sur les notations Asymptotiques
Dire si les affirmations suivantes sont vraies, pour toute fonction f de N dans R+ :
- $$2^{(n+1)} \in O(2^n)$$
- $$(n+1)! \in O(n!)$$
- $$f(n) \in O(n) \Rightarrow (f(n))^2 \in O(n^2)$$
- $$f(n) \in O(n) \Rightarrow 2^{(f(n))} \in O(2^n)$$
- $$n^n \in O(2^n)$$
Soient f(x) et g(x) des fonctions positives asymptotiquement, prouver ou démentir les affirmations suivantes :
- $$f(n) = O(g(n)) \Rightarrow g(n) = O(f(n))$$
- $$f(n) + g(n) = \Theta(\min(f(n), g(n)))$$
- $$f(n) = O(g(n)) \Rightarrow 2f(n) = O(2g(n))$$
Pour chacune des récurrences suivantes, donnez une expression pour le temps d'exécution T(n) si la récurrence peut être résolue avec le Théorème du Maître. Dans le cas contraire, indiquez que le Théorème du Maître ne s'applique pas :
- $$T(n) = 3T(n/2) + n^2$$
- $$T(n) = 4T(n/2) + n^2$$
- $$T(n) = T(n/2) + 2n$$
- $$T(n) = 2nT(n/2) + nn$$
- $$T(n) = 16T(n/4) + n$$
- $$T(n) = 2T(n/2) + n \log n$$
- $$T(n) = 2T(n/2) + n/ \log n$$
- $$T(n) = 2T(n/4) + n^{0.51}$$
- $$T(n) = 0.5T(n/2) + 1/n$$
- $$T(n) = 16T(n/4) + n!$$
- $$T(n) = \sqrt{2}T(n/2) + \log n$$
- $$T(n) = 3T(n/2) + n$$
- $$T(n) = 3T(n/3) + \sqrt{n}$$
- $$T(n) = 4T(n/2) + cn$$
- $$T(n) = 3T(n/4) + n \log n$$
- $$T(n) = 3T(n/3) + n/2$$
- $$T(n) = 6T(n/3) + n^2 \log n$$
- $$T(n) = 4T(n/2) + n/ \log n$$
- $$T(n) = 64T(n/8) - n^2 \log n$$
- $$T(n) = 7T(n/3) + n^2$$
- $$T(n) = 4T(n/2) + \log n$$
- $$T(n) = T(n/2) + n(2 - \cos n)$$