fiche

Complexité

Notations de Landeau

• \(O\left( f(n) \right)\): Majoration par \(Af(n),A \in {\mathbb{R}}^{+}\)

• \(\Theta\): Minoration par \(Af(n),A \in {\mathbb{R}}^{+}\)

• \(\Omega\): Majoration par\(Af(n),A \in {\mathbb{R}}^{+}\), Minoration par \(Bf(n),B \in {\mathbb{R}}^{+}\)

Dichotomie

Théorème maitre

On sépare un problème en \(a\) sous problèmes de taille \(\frac{n}{b}\), combinés en \(O\left( n^{d} \right)\), ie:
\(T(n) = aT\left( \frac{n}{b} \right) + O\left( n^{d} \right)\)

On a alors \[T(n) = \begin{cases} O\left( n^{d} \right) & \text{ si }a < b^{d} \\ O\left( n^{d}\log(n) \right) & \text{ si }a = b^{d} \\ O\left( n^{\log_{b}(a)} \right) & \text{ si }a > b^{d} \end{cases}\]

Solutions d’une suite linéaire récurrente d’odre 2

Soit \((u)\) une suite réelle tq: \(u_{n} = au_{n - 1} + bu_{n - 2}\)
On peut alors poser le polynome caractéristique: \(r^{2} - ar - b\)

On procède alors à la résolution de l’équation. Dans le cas où le discriminant est strictement positif (toujours le cas chez nous car a > 0 et b > 0), alors (u) est de la forme:
\(u_{n} = \lambda r_{1}^{n} + \mu r_{2}^{n}\) (\(\lambda\) et \(\mu\) à déterminer à partir de \(u_{0}\) et \(u_{1}\))

Dans la pratique
On pose \((u)\) le nombre d’appel récursif de la fonction
On calcule le polynome caractéristique
On trouve l’unique solution positive Alors la complexité de l’algo est \(O\left( r^{n} \right)\)

Graphes

Définitions

Arbre couvrant

Arbre couvrant de cout minimal

Arborescence couvrante depuis un sommet

Algo de Prim

Algo de Dijkstra

Algorithmes glouton

Définition

Algo glouton

Algo de Kruskal

Complexité

Cas général: \(O\left( m\log m \right)\)
Coup amorti (en rebalançant l’arbre): \(O\left( n + m\alpha(n,m) \right)\) avec \(\alpha\) la réciproque de la fonction d’Ackerman, qui croit extremement lentement.

Règles liées aux cycles

Définitions

Cocycle

Approximant

Un couple \((X,Y)\) de parties disjointes de \(A\) est un approximant s’il existe un arbre optimal \(H^{\ast}\) tel que \(X \subset H \ast\) et \(Y \subset A\backslash H \ast\).

Règle des cocycles

Soit \((X,Y)\) un approximant, soit \(C\) un cocycle dont chaque arête est rouge ou blanche ; Soit \(e\) une arête blanche de \(C\) de coût minimum. Alors \(\left( X \cup \left\{ e \right\},Y \right)\) est un approximant

Règle des cycles

Soit \((X,Y)\) un approximant, soit \(C\) un cycle dont chaque arête est bleue ou blanche. Soit \(e\) une arête blanche de \(C\) de coût maximum. \(\left( X,Y \cup \left\{ e \right\} \right)\) est un approximant .

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