L'efficacité d'un algorithme dépend de deux paramètres :
- Complexité temporelle
- Complexité spatiale
Complexité temporelle :
La complexité temporelle est définie comme le nombre de fois qu'un jeu d'instructions particulier est exécuté plutôt que comme le temps total nécessaire. En effet, le temps total dépend également de certains facteurs externes comme le compilateur utilisé, la vitesse du processeur, etc.
Complexité spatiale :
La complexité spatiale est l'espace mémoire total requis par le programme pour son exécution.
Les deux sont calculés en fonction de la taille d’entrée (n). Une chose importante ici est que malgré ces paramètres, l'efficacité d'un algorithme dépend également de la nature et taille de le saisir.
Types de complexité temporelle :
- Meilleure complexité temporelle : Définissez l'entrée pour laquelle l'algorithme prend le moins de temps ou le temps minimum. Dans le meilleur des cas, calculez la limite inférieure d'un algorithme. Exemple : Dans la recherche linéaire, lorsque les données de recherche sont présentes au premier emplacement de données volumineuses, le meilleur des cas se produit.
- Complexité temporelle moyenne : Dans le cas moyen, prenez toutes les entrées aléatoires et calculez le temps de calcul pour toutes les entrées.
Et puis nous le divisons par le nombre total d’entrées. - Pire complexité temporelle : Définissez l'entrée pour laquelle l'algorithme prend beaucoup de temps ou un temps maximum. Dans le pire des cas, calculez la limite supérieure d'un algorithme. Exemple : dans la recherche linéaire, lorsque les données de recherche sont présentes au dernier emplacement de données volumineuses, le pire des cas se produit.
Voici une fiche de révision rapide à laquelle vous pourrez vous référer à la dernière minute :
| Algorithme | Complexité temporelle | Complexité spatiale | ||
|---|---|---|---|---|
| Meilleur | Moyenne | Pire | Pire | |
| Tri de sélection | Sur2) | Sur2) | Sur2) | O(1) |
| Tri à bulles | Sur) | Sur2) | Sur2) | O(1) |
| Tri par insertion | Sur) | Sur2) | Sur2) | O(1) |
| Tri en tas | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(1) |
| Tri rapide | O(n log(n)) | O(n log(n)) | Sur2) | Sur) |
| Tri par fusion | O(n log(n)) | O(n log(n)) | O(n log(n)) | Sur) |
| Tri par seau | O(n+k) | O(n+k) | Sur2) | Sur) |
| Trier la base | O (nk) | O (nk) | O (nk) | O(n+k) |
| Compte Trier | O(n+k) | O(n+k) | O(n+k) | Flèche) |
| Tri des coquilles | O(n log(n)) | O(n log(n)) | Sur2) | O(1) |
| Tim Trier | Sur) | O(n log(n)) | O(nlog(n)) | Sur) |
| Tri par arbre | O(n log(n)) | O(n log(n)) | Sur2) | Sur) |
| Tri des cubes | Sur) | O(n log(n)) | O(n log(n)) | Sur) |
Regarde aussi:
- Rechercher et trier des articles
- Questions GATE de l’année précédente sur le tri
- Complexité temporelle et spatiale du tri par insertion
- Complexité temporelle et spatiale du tri par sélection
- Complexité temporelle et spatiale du tri à bulles
- Complexité temporelle et spatiale du tri rapide
- Complexité temporelle et spatiale du tri par fusion
- Complexité temporelle et spatiale de l'algorithme de tri Radix