Table des matières:
Définition - Que signifie la complexité temporelle?
La complexité temporelle est un concept en informatique qui traite de la quantification du temps nécessaire à un ensemble de codes ou d'algorithmes pour traiter ou s'exécuter en fonction de la quantité d'entrée.
En d'autres termes, la complexité temporelle est essentiellement l'efficacité, ou le temps nécessaire à une fonction de programme pour traiter une entrée donnée.
Techopedia explique la complexité temporelle
La complexité temporelle est simplement une mesure du temps nécessaire à une fonction ou une expression pour terminer sa tâche, ainsi que le nom du processus pour mesurer ce temps. Il peut être appliqué à presque tous les algorithmes ou fonctions, mais il est plus utile pour les fonctions récursives. Il est inutile de mesurer la complexité temporelle pour des applications telles que l'extraction du nom d'utilisateur et du mot de passe d'une base de données à des fins de comparaison ou simplement la sauvegarde des données, que ce soit 20 ms ou 5 ms; ce serait plus dans la ligne du temps d'accès. Cela n'a rien à voir avec le souci de son temps d'exécution, mais plutôt que la différence est négligeable. Cependant, s'il existe une fonction récursive qui peut être appelée plusieurs fois, la détermination et la compréhension de la source de sa complexité temporelle peuvent aider à raccourcir le temps de traitement global de, disons, de 600 ms à 100 ms.
La complexité temporelle s'exprime généralement dans la «grande notation O», mais il existe d'autres notations. Il s'agit d'une représentation mathématique de la limite supérieure du facteur d'échelle pour un algorithme et est écrite comme O (Nn), "N" étant le nombre d'entrées et "n" étant le nombre d'expressions en boucle. Par exemple, nous avons l'algorithme:
numbers = {5, 6, 10, 11, 2}; foreach (number as number1)
{
foreach(number as number2)
{
statements; } }
numbers = {5, 6, 10, 11, 2};
foreach (number as number1)
{
foreach(number as number2)
{
statements; } }
numbers = {5, 6, 10, 11, 2};
foreach (number as number1)
{
foreach(number as number2) {
statements; } }
numbers = {5, 6, 10, 11, 2};
foreach (number as number1)
{
foreach(number as number2)
{
statements; } }
numbers = {5, 6, 10, 11, 2};
foreach (number as number1)
{
foreach(number as number2)
{
statements; } }
Il y a cinq entrées dans le tableau "nombres" et la boucle "foreach" est répétée deux fois. Par conséquent, une croissance exponentielle du temps de traitement se produit lorsque le nombre d'entrées et le nombre de boucles augmentent.
