|
impliquent des problèmes d'informatique souvent plus d'une solution , et chaque solution est atteinte en suivant un ensemble de règles , aussi connu comme un algorithme. Big O notation fournit une méthode pour décrire l'efficacité d'un algorithme - en d'autres termes , le temps qu'il faut pour un algorithme à exécuter en fonction de la taille de l'entrée de cet algorithme. Contexte
Big O notation - également connu comme le symbole de Landau, d'après le mathématicien juif allemand , Edmund Landau - décrit le taux de croissance d'une fonction, également connu sous le nom de son «ordre », d'où l' lettre O notation Big " O " du capital est destiné à mesurer la performance d'un algorithme lui-même , plutôt que le matériel sur lequel l'algorithme est exécuté. Un morceau de matériel peut être plus rapide ou plus lent que l'autre par un facteur constant , de sorte que tous les facteurs constants sont retirés de notation Big O .
Constant Temps de marche
Un algorithme qui prend toujours plus ou moins en même temps d'exécuter , indépendamment de la taille de l'entrée , qui est dit pour avoir le temps de marche " constant " . En O notation Big, ce type d'algorithme est connu comme un algorithme de " l'ordre 1 " et est notée O (1) . Des exemples de O (1) algorithmes comprennent pousser ou sauter des données vers et à partir d'une pile de programmation , et la récupération d'un seul élément de données d'un tableau quand on sait sa position. Ces algorithmes effectuent uniquement un certain nombre de mesures , peu importe la taille de l'entrée devient .
Linéaire Temps de marche
Un algorithme dont la durée de l'augmentation proportionnellement , ou en mode linéaire, avec la taille de son entrée qui est dit pour avoir le temps de fonctionnement "linéaire" . Dans la notation O grande , ce type d'algorithme est connu comme un " ordre n " algorithme et est désigné par O (n) , ce qui indique que le temps nécessaire pour l'algorithme afin de fonctionner augmente linéairement à mesure que le nombre d'éléments de données , "n , " augmente . Un exemple simple d' un algorithme O (n) est un algorithme qui calcule le total d' une liste de numéros ; une addition est nécessaire pour chaque élément de la liste , de sorte que le nombre d'additions est la même que le nombre d'éléments < br . >
quadratique Temps de marche
un algorithme dont la durée de l'augmentation d'un facteur n ^ 2 lorsque la taille de son entrée augmente d'un facteur de "n" est dit avoir le temps de fonctionnement " quadratique " . En O notation Big, ce type d'algorithme est connu comme un ordre n ^ 2 algorithme , ou simplement un algorithme quadratique, et est notée O (n ^ 2 ) . Des exemples de O algorithmes ( n ^ 2 ) comprennent des algorithmes de tri, telles que tri par insertion et tri à bulles , dans lequel doubler la taille de l'entrée quadruple le temps d'exécution.
|
