Qu’est-ce que logn ?

La version courte est que c’est un terme informatique geek qui s’est aussi avéré être assez court pour que je l’aime comme nom de domaine. Malgré ce que les autres peuvent vous dire, ce n’est pas une erreur d’orthographe de « login ». De plus, on a tendance à le prononcer comme « log » suivi de la lettre « n ».

La version longue est que c’est le terme utilisé pour décrire une classe d’algorithmes très efficaces.Si vous voulez bien me permettre une petite leçon…

Complexité temporelle

En informatique, les algorithmes sont souvent comparés par la quantité de temps ou de mémoire qu’ils consomment pour effectuer une tâche. Afin de rendre ces comparaisons justes et faciles à comprendre, nous les analysons en nous basant sur la relation entre la taille de la tâche et le nombre d’étapes nécessaires à sa réalisation.

Par exemple, supposons que vous vouliez faire la moyenne d’une liste de valeurs numériques. Pour ce faire, vous auriez besoin d’additionner tous les nombres, puis de diviser par le nombre de valeurs que vous avez. Le nombre d’étapes est directement lié au nombre de valeurs : si vous doublez le nombre de valeurs à moyenner, vous pouvez vous attendre à ce que cela prenne deux fois plus de temps. C’est un exemple de complexité linéaire : à mesure que le nombre d’éléments (abrégé en n) augmente, le temps nécessaire pour accomplir la tâche augmente au même rythme.

Vous pouvez certainement faire bien pire que le temps linéaire ; de nombreuses tâches nécessitent un temps polynomial ou même exponentiel pour être accomplies ! Le tri de listes de nombres est un bon exemple ; vous devez faire plusieurs passages sur les donnéespour tout trier dans un ordre final.

Cependant, il y a aussi certains algorithmes qui sont meilleurs que le temps linéaire. Prenons l’exemple d’un jeu de devinette où un humain pense à un nombre compris entre un et 100, et l’ordinateur doit deviner ce que c’est. Si l’ordinateur se trompe, l’humain indique à l’ordinateur si la réponse est « supérieure » ou « inférieure » à l’estimation. En choisissant les devinettes avec soin, cette information permet à l’ordinateur d’éliminer la moitié des nombres restants à chaque devinette (en choisissant toujours un nombre au milieu de l’ensemble des nombres possibles).

Parce que chaque devinette divise en deux la réserve de nombres restants, ces moitiés répétées se composent et créent un exposant inverse : un alogarithme. En fait, le nombre d’étapes pour résoudre le problème augmente linéairement alors que l’espace du problème croît exponentiellement. D’une autre manière, le fait de doubler la taille du problème n’entraîne qu’une seule étape supplémentaire (comparez cela à un algorithme linéaire, où le fait de doubler la taille du problème double également le nombre d’étapes). Nous abrégeons cette relation par logn, montrant que lorsque n (la taille du problème) devient plus grand, le nombre d’étapes n’est que le logarithme de ce nombre.

Donc, les algorithmes logarithmiques sont très efficaces et bien considérés.J’ai pensé qu’il serait amusant de donner leur nom à mon domaine.

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée.