Complexité algorithmique

De Banane Atomic
Révision datée du 5 février 2017 à 14:18 par Nicolas (discussion | contributions)
(diff) ← Version précédente | Voir la version actuelle (diff) | Version suivante → (diff)
Aller à la navigationAller à la recherche

Liens

Notation "grand O"

Une complexité en O(N) signifie que l'algorithme exécutera environ un nombre d'opérations de l'ordre de grandeur de N.

  • Ex: N ou 2*N ou N+10 ou 10*N + N/2
  • Mais pas: N² ni N*log(N)

Considérant N possiblement très grand, on néglige les termes de plus petits.

Méthodes C#

Méthode Complexité
List<T>.Sort On average, it is an O(N*log(N)) operation;
in the worst case it is an O(N²) operation.
List<T>.Contains It performs a linear search; therefore, this method is an O(N) operation.
Dictionary<TKey, TValue>.ContainsValue It performs a linear search; therefore, the average execution time is proportional to Count.
That is, this method is an O(N) operation.
SortedList.Contains It uses a binary search algorithm; therefore, this method is an O(log(N)) operation.
Dictionary<TKey, TValue>.ContainsKey It approaches an O(1) operation.
List<T>.Add If Count is less than Capacity, this method is an O(1) operation.
If the capacity needs to be increased to accommodate the new element, this method becomes an O(N) operation.