Complexite

Classes de complexité

complexité logarithmique

• O(1) : constant
• O(n) : linéaire
• O(log n) : logarithmique
• O(n log n) : quasi-linéaire
• O(n²) : quadratique
• O(n³) : cubique
• O(n^k) : polynomial
• O(2ⁿ) : exponentielle
• O(n!) : factorielle

Problème complexe

Problème du voyageur de commerce

• problème NP-complet
• O(n!)
• 10 villes : 3 628 800

Problème du sac à dos

knapack problem

• problème NP-complet
• O(2ⁿ)
• 20 objets : 1 048 576

Problème du plus court chemin

aussi appelé longest common subsequence

• problème NP-complet
• O(n²)
• 100 villes : 10 000

Stable marriage problem

aussi appelé problème des mariages stables (stable matching problem) ou problème des épouses de Gale et Shapley (Gale–Shapley algorithm)

• problème NP-complet
• O(n²)
• 100 personnes : 10 000

Alago 1 : Gape-Shapley O(n²)

vertex cover

aussi appelé couverture par sommets

Algo 1 : brute force O(2ⁿ)

glouton

Algo 2 : approximation O(n) Algo 3 : heuristique du degré O(n²)

clique

Algo 1 : brute force O(2ⁿ) Algo 2 : approximation O(n)

independent set

Algo 1 : brute force O(2ⁿ) Algo 2 : approximation O(n)

modularité

Algo 1 : brute force O(2ⁿ) Algo 2 : approximation O(n)

manathan distance

Algo 1 : brute force O(n²)

heuriqtique

• 2-approximation
• degree