01

Rappels sur les preuves d’algorithmes et analyse de complexité

Soit \(n \in {\mathbb{N}}\)

==== \(C = 10^{4}\)    ==== \(C = 38\)    ==== \(C = 2^{100}\)    ==== \(C = \frac{1}{10}\)    ==== \(C_{1} = 5,C_{2} = 25\)

V \[\begin{array}{r} f \sim O(h)\text{ donc }\exists C \in {\mathbb{R}}^{+}\forall n \in {\mathbb{N}},f(n) \leq Ch(n) \\ g \sim O(h)\text{ donc }\exists D \in {\mathbb{R}}^{+}\forall n \in {\mathbb{N}},g(n) \leq Dh(n) \\ \text{d'où }\forall n \in {\mathbb{N}},f(n) + g(n) \leq (C + D)h(n) \end{array}\]

F (voir prochain)

\(C^{2} \neq C\)

V

\[\begin{array}{r} f \sim O(h)\text{ donc }\exists C \in {\mathbb{R}}^{+}\forall n \in {\mathbb{N}},f(n) \leq Ch(n) \\ g \sim O(h)\text{ donc }\exists D \in {\mathbb{R}}^{+}\forall n \in {\mathbb{N}},g(n) \leq Dh(n) \\ \text{d'où }\forall n \in {\mathbb{N}},f(n) \times g(n) \leq CDh(n) \end{array}\]

V \[\begin{array}{r} f \sim O(h)\text{ donc }\exists C \in {\mathbb{R}}^{+}\forall n \in {\mathbb{N}},f(n) \geq Ch(n) \\ g \sim O(h)\text{ donc }\exists D \in {\mathbb{R}}^{+}\forall n \in {\mathbb{N}},g(n) \geq Dh(n) \\ \text{d'où }\forall n \in {\mathbb{N}},f(n) + g(n) \geq (C + D)h(n) \end{array}\]

F

F

F faux en tout point, vrai à partir d’un certain rang

F faux en tout point, vrai à partir d’un certain rang

=== (a) \(C_{1} = 1,C_{2} = \frac{1}{1} - a\text{ car }\lim\left( 1 - \frac{a^{n + 1}}{1} - a \right) = \frac{1}{1} - a\)

\(2^{n}\). l’ensemble \(\mathbb{N}\) est minoré

mbeeeeeuh

\(O\left( a\log(ab) \right)\text{ car }n = \log(p) = \log(ab)\text{ à la fin}\)

Page incomplète ou erronée? Contribuez sur le repo