Télécharger au format pdf
02
Rappels sur les preuves d’algorithmes et analyse de complexité
On peut séparer l’échiquier dans des groupes où placer les triominos est trivial.
\(T(n) = O\left( n^{2} \right)\)
\(T(n) = O\left( n\log(n) \right)\)
\(T(n) = O\left( n^{\log(2)} \right) = O(n)\)
\(T(n) = O\left( \log(n) \right)\)
Flemme cf photo, faut que je resorte fletcher. L’arbre est asymétrique, plus cours sur la gauche qu’à droite.
On fait n opération en coup n à chaque étage puis on brange à gauche en \(\log_{3}(n)\) et à droite en \(\log_{\frac{3}{2}}(n)\)
D’où \(T(n) = O\left( n^{\log_{\frac{3}{2}}(2)} \right)\)
Non, car l’expression de \(T(n)\) ne
satisfait pas les hypothèses. On peut majorer pour l’appliquer:
\(T(n) = T\left( \left\lceil \frac{n}{3}
\right\rceil \right) + T\left( \left\lfloor \frac{2n}{3} \right\rfloor
\right) + n \leq 2T\left( \left\lfloor \frac{2n}{3} \right\rfloor
\right) + n\)
\(T(n) = 4 \times \left( \frac{n}{2} \right)^{2} = n^{2}\)
\(T(n) = 8T\left( \frac{n}{2} \right) + O\left( n^{2} \right)\)
En appliquant le théorème maitre, on a:
\(T(n) = O\left( n^{\log_{2}(8)} \right) =
O\left( n^{3} \right)\)
\(T(n) = 7T\left( \frac{n}{2} \right) + n^{2}\)
En appliquant le théorème maitre, on a:
\(T(n) = O\left( n^{\log_{2}(7)}
\right)\)
\[\begin{aligned} T(n) = \sum_{i = 1}^{n}\sum_{j = i}^{n}\sum_{k = i}^{j}O(1) & = O\left( \sum_{i = 1}^{n}\sum_{j = i}^{n}\sum_{k = i}^{j}(j - i + 1) \right) \\ & = O\left( \sum_{i = 1}^{n}\sum_{j = i}^{n - i + 1}j \right) \\ & = O\left( \sum_{i = 1}^{n}\frac{(n - i + 1)(n - i + 2)}{2} \right) \\ & = O\left( \sum_{i = 1}^{n - 1}\frac{(i + 1)(i + 2)}{2} \right) = O\left( n^{3} \right) \end{aligned}\]
On se débarasse de k, ie on avance et on somme sur j, en gardant le maximum à l’aller
\(\text{stm}_{3} = \max\limits_{i \leq m}\sum_{k = i}^{m}A\lbrack k\rbrack + \max\limits_{i \geq m + 1}\sum_{k = i}^{n}A\lbrack k\rbrack\)
\(\text{stm}(A) = \max(\text{stm}_{1},\text{ stm}_{2},\text{ stm}_{3})\)
\(T(n) = 2T\left( \frac{n}{2} \right) +
O(n)\)
D’où
\(T(n) = O\left( n\log(n) \right)\)
On a \(\text{pref}(A) = \text{ stm}_{1}\) et \(\text{suff}(A) = \text{ stm}_{2}\), or \(\text{stm}_{1} + \text{ stm}_{2} \neq \text{ stm}_{3}\)
Page incomplète ou erronée? Contribuez sur le repo