Complexité algorithmique
De Banane Atomic
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. |
