Complexité de l'algorithme

Bonjour! La conférence d'aujourd'hui sera un peu différente des autres. Il diffère en ce sens qu'il n'est qu'indirectement lié à Java. Cependant, ce sujet est très important pour tout programmeur. Nous parlerons d' algorithmes . Qu'est-ce qu'un algorithme ? En termes simples, il s'agit d'une certaine séquence d'actions qui doivent être effectuées pour obtenir le résultat souhaité . Nous utilisons souvent des algorithmes dans la vie de tous les jours. Par exemple, chaque matin, vous êtes confronté à une tâche : venir à l'école ou au travail, et en même temps être :

• Habillé
• Faire le ménage
• Bien nourri

Quel algorithme vous permettra d’arriver à ce résultat ?

1. Réveillez-vous avec un réveil.
2. Prenez une douche, lavez-vous le visage.
3. Préparer le petit-déjeuner, préparer le café/thé.
4. Manger.
5. Si vous n’avez pas repassé vos vêtements depuis le soir, repassez-les.
6. S'habiller.
7. Quitter la maison.

Cette séquence d'actions vous permettra certainement d'obtenir le résultat souhaité. En programmation, tout l’intérêt de notre travail est de constamment résoudre des problèmes. Une partie importante de ces tâches peut être réalisée à l’aide d’algorithmes déjà connus. Par exemple, vous êtes confronté à une tâche : trier une liste de 100 noms dans un tableau . Cette tâche est assez simple, mais elle peut être résolue de différentes manières. Voici une solution : Algorithme de tri des noms par ordre alphabétique :

1. Achetez ou téléchargez sur Internet « Dictionnaire des noms de personnes russes » édition 1966.
2. Trouvez tous les noms de notre liste dans ce dictionnaire.
3. Notez sur une feuille de papier sur quelle page du dictionnaire se trouve le nom.
4. Mettez les noms dans l'ordre en utilisant les notes sur une feuille de papier.

Une telle séquence d’actions nous permettra-t-elle de résoudre notre problème ? Oui, cela le permettra tout à fait. Cette solution sera-t-elle efficace ? À peine. Nous arrivons ici à une autre propriété très importante des algorithmes : leur efficacité . Le problème peut être résolu de différentes manières. Mais aussi bien en programmation que dans la vie de tous les jours, on choisit la méthode qui sera la plus efficace. Si votre tâche est de préparer un sandwich avec du beurre, vous pouvez bien sûr commencer par semer du blé et traire une vache. Mais ce sera une solution inefficace – cela prendra beaucoup de temps et coûtera beaucoup d’argent. Pour résoudre votre problème simple, vous pouvez simplement acheter du pain et du beurre. Et l'algorithme avec le blé et la vache, bien qu'il permette de résoudre le problème, est trop complexe pour l'appliquer dans la pratique. Pour évaluer la complexité des algorithmes en programmation, une notation spéciale a été créée appelée Big-O (« big O ») . Big-O permet d'estimer dans quelle mesure le temps d'exécution d'un algorithme dépend des données qui y sont transmises . Regardons l'exemple le plus simple : le transfert de données. Imaginez que vous deviez transmettre des informations sous forme de fichier sur une longue distance (par exemple 5 000 kilomètres). Quel algorithme sera le plus efficace ? Cela dépend des données avec lesquelles il doit travailler. Par exemple, nous avons un fichier audio de 10 mégaoctets. Dans ce cas, l’algorithme le plus efficace serait de transférer le fichier via Internet. Cela ne prendra que quelques minutes ! Exprimons donc à nouveau notre algorithme : « Si vous devez transférer des informations sous forme de fichiers sur une distance de 5 000 kilomètres, vous devez utiliser la transmission de données sur Internet. Super. Analysons-le maintenant. Est-ce que cela résout notre problème ? En général, oui, cela résout complètement le problème. Mais que dire de sa complexité ? Hmm, c'est maintenant que les choses deviennent intéressantes. Le fait est que notre algorithme dépend beaucoup des données entrantes, à savoir la taille des fichiers. Nous avons maintenant 10 mégaoctets et tout va bien. Et si nous devions transférer 500 mégaoctets ? 20 gigaoctets ? 500 téraoctets ? 30 pétaoctets ? Notre algorithme va-t-il cesser de fonctionner ? Non, toutes ces quantités de données peuvent toujours être transférées. Est-ce que cela prendra plus de temps ? Oui, il sera! Nous connaissons désormais une caractéristique importante de notre algorithme : plus la taille des données à transférer est grande, plus l'algorithme mettra du temps à s'exécuter . Mais nous aimerions comprendre plus précisément à quoi ressemble cette relation (entre la taille des données et le temps nécessaire à leur transfert). Dans notre cas, la complexité de l'algorithme sera linéaire. « Linéaire » signifie qu'à mesure que le volume de données augmente, le temps de transmission augmentera à peu près proportionnellement. S'il y a 2 fois plus de données, il faudra 2 fois plus de temps pour les transférer. S'il y a 10 fois plus de données, le temps de transfert augmentera 10 fois. En utilisant la notation Big-O, la complexité de notre algorithme est définie comme O(N) . Il est préférable de retenir cette notation pour référence future ; elle est toujours utilisée pour les algorithmes à complexité linéaire. Attention : nous ne parlons pas du tout ici de diverses choses « variables » : la vitesse d'Internet, la puissance de notre ordinateur, etc. Lorsque l’on évalue la complexité d’un algorithme, cela n’a tout simplement pas de sens : de toute façon, nous n’avons aucun contrôle sur celui-ci. Big-O évalue l’algorithme lui-même, quel que soit « l’environnement » dans lequel il devra travailler. Continuons avec notre exemple. Disons qu'il s'avère finalement que la taille des fichiers à transférer est de 800 téraoctets. Si nous les transmettons sur Internet, le problème sera bien sûr résolu. Il n'y a qu'un seul problème : la transmission sur une liaison moderne standard (à 100 mégabits par seconde) que la plupart d'entre nous utilisons à la maison prendra environ 708 jours. Presque 2 ans! :O Donc, notre algorithme n'est clairement pas adapté ici. Il nous faut une autre solution ! Du coup, le géant de l’informatique Amazon vient à notre secours ! Son service Amazon Snowmobile permet de charger de grandes quantités de données dans des unités de stockage mobiles et de les livrer à l'adresse souhaitée par camion ! Nous avons donc un nouvel algorithme ! "Si vous devez transférer des informations sous forme de fichiers sur une distance de 5 000 kilomètres et que le processus prendra plus de 14 jours lors du transfert via Internet, vous devez utiliser le transport par camion d'Amazon." Le chiffre de 14 jours a été choisi ici au hasard : disons que c’est la durée maximale que l’on peut se permettre. Analysons notre algorithme. Et la vitesse ? Même si le camion roule à seulement 50 km/h, il parcourra 5 000 kilomètres en seulement 100 heures. Cela fait un peu plus de quatre jours ! C'est bien mieux que l'option de transmission par Internet. Qu’en est-il de la complexité de cet algorithme ? Sera-t-il également linéaire, O(N) ? Non, ce ne sera pas le cas. Après tout, le camion ne se soucie pas de la quantité que vous chargez : il roulera toujours à peu près à la même vitesse et arrivera à l'heure. Que nous ayons 800 téraoctets, soit 10 fois plus de données, le camion y arrivera quand même en 5 jours. En d’autres termes, l’algorithme de livraison des données par camion est d’une complexité constante . « Constant » signifie que cela ne dépend pas des données transmises à l'algorithme. Mettez une clé USB de 1 Go dans le camion et elle arrivera dans 5 jours. Mettez-y des disques contenant 800 téraoctets de données et cela arrivera dans 5 jours. Lors de l'utilisation de Big-O, une complexité constante est notée O(1) . Depuis que nous connaissons O(N) etO(1) , regardons maintenant d'autres exemples de « programmeurs » :) Disons que l'on vous donne un tableau de 100 nombres et que la tâche est d'imprimer chacun d'eux sur la console. Vous écrivez une boucle régulière forqui effectue cette tâche

int[] numbers = new int[100];
// ..заполняем массив числами

for (int i: numbers) {
   System.out.println(i);
}

Quelle est la complexité de l’algorithme écrit ? Linéaire, O(N). Le nombre d'actions que le programme doit effectuer dépend exactement du nombre de nombres qui lui ont été transmis. S'il y a 100 nombres dans le tableau, il y aura 100 actions (sorties à l'écran). S'il y a 10 000 nombres dans le tableau, 10 000 actions devront être effectuées. Notre algorithme peut-il être amélioré ? Non. Dans tous les cas, nous devrons effectuer N passages dans le tableau et effectuer N sorties vers la console. Regardons un autre exemple.

public static void main(String[] args) {

   LinkedList<Integer> numbers = new LinkedList<>();
   numbers.add(0, 20202);
   numbers.add(0, 123);
   numbers.add(0, 8283);
}

Nous en avons un vide LinkedListdans lequel nous insérons plusieurs nombres. Nous devons estimer la complexité de l'algorithme d'insertion d'un seul nombre dans LinkedListnotre exemple et comment il dépend du nombre d'éléments dans la liste. La réponse est O(1) - complexité constante . Pourquoi? Attention : à chaque fois nous insérons un numéro en début de liste. De plus, comme vous vous en souvenez, lors de l'insertion de nombres dans LinkedListdes éléments, ils ne sont décalés nulle part - les liens sont redéfinis (si vous avez soudainement oublié comment fonctionne LinkedList, jetez un œil à l'une de nos anciennes conférences ). Si maintenant le premier nombre de notre liste est le nombre х, et que nous insérons le nombre y au début de la liste, il suffit de :

x.previous  = y;
y.previous = null;
y.next = x;

Pour cette redéfinition des références, peu importe pour nous combien de nombres il existe actuellementLinkedList - au moins un, au moins un milliard. La complexité de l'algorithme sera constante - O(1).

Complexité logarithmique

Ne pas paniquer! :) Si le mot « logarithmique » vous donne envie de fermer la conférence et de ne pas poursuivre la lecture, attendez quelques minutes. Il n'y aura pas de difficultés mathématiques ici (il y a beaucoup d'explications de ce type ailleurs), et nous analyserons tous les exemples « sur les doigts ». Imaginez que votre tâche consiste à trouver un nombre spécifique dans un tableau de 100 nombres. Plus précisément, vérifiez s'il est là. Dès que le numéro recherché est trouvé, la recherche doit être arrêtée et l'entrée « Le numéro recherché a été trouvé ! » doit s'afficher dans la console. Son index dans le tableau = .... » Comment résoudriez-vous un tel problème ? Ici, la solution est évidente : vous devez parcourir les éléments du tableau un par un, en commençant par le premier (ou le dernier) et vérifier si le numéro actuel coïncide avec celui souhaité. En conséquence, le nombre d'actions dépend directement du nombre d'éléments du tableau. Si nous avons 100 nombres, nous devons alors passer à l’élément suivant 100 fois et vérifier 100 fois si le numéro correspond. S'il y a 1 000 nombres, alors il y aura 1 000 étapes de vérification. Il s'agit évidemment d'une complexité linéaire, O(N) . Nous allons maintenant ajouter une précision à notre exemple : le tableau dans lequel vous devez trouver un nombre est trié par ordre croissant . Est-ce que cela change quelque chose à notre tâche ? On peut toujours rechercher le numéro souhaité par force brute. Mais nous pouvons plutôt utiliser l' algorithme de recherche binaire bien connu . Dans la rangée supérieure de l'image, nous voyons un tableau trié. Dans celui-ci, nous devons trouver le nombre 23. Au lieu de parcourir les nombres, nous divisons simplement le tableau en 2 parties et vérifions le nombre moyen dans le tableau. Nous trouvons le numéro qui se trouve dans la cellule 4 et le vérifions (deuxième ligne de l'image). Ce nombre est 16 et nous recherchons 23. Le nombre actuel est inférieur. Qu'est-ce que cela signifie? Que tous les nombres précédents (qui se situent jusqu'au nombre 16) n'ont pas besoin d'être vérifiés : ils seront certainement inférieurs à celui que nous recherchons, car notre tableau est trié ! Continuons la recherche parmi les 5 éléments restants. Faites attention:Nous n'avons effectué qu'une seule vérification, mais nous avons déjà éliminé la moitié des options possibles. Il ne nous reste que 5 éléments. Nous allons répéter notre étape - divisez à nouveau le tableau restant par 2 et prenez à nouveau l'élément du milieu (ligne 3 sur la figure). Ce nombre est 56, et il est plus grand que celui que nous recherchons. Qu'est-ce que cela signifie? Que nous supprimons 3 options supplémentaires - le nombre 56 lui-même et deux nombres après (ils sont définitivement supérieurs à 23, car le tableau est trié). Il ne nous reste que 2 nombres à vérifier (la dernière ligne de la figure) - des nombres avec des indices de tableau 5 et 6. Nous vérifions le premier d'entre eux, et c'est ce que nous recherchions - le nombre 23 ! Son indice = 5 ! Examinons les résultats de notre algorithme, puis nous comprendrons sa complexité. (D'ailleurs, vous comprenez maintenant pourquoi on l'appelle binaire : son essence est de diviser constamment les données par 2). Le résultat est impressionnant ! Si nous recherchions le nombre souhaité en utilisant la recherche linéaire, nous aurions besoin de 10 vérifications, mais avec la recherche binaire nous l'avons fait en 3 ! Dans le pire des cas, il y en aurait 4 si à la dernière étape le numéro dont nous avions besoin s'avérait être le deuxième, et non le premier. Qu’en est-il de sa complexité ? C'est un point très intéressant :) L'algorithme de recherche binaire dépend beaucoup moins du nombre d'éléments dans le tableau que l'algorithme de recherche linéaire (c'est-à-dire une simple énumération). Avec 10 éléments dans le tableau, la recherche linéaire nécessitera un maximum de 10 vérifications et la recherche binaire nécessitera un maximum de 4 vérifications. La différence est de 2,5 fois. Mais pour un tableau de 1000 éléments, la recherche linéaire nécessitera 1000 vérifications, et la recherche binaire n'en nécessitera que 10 ! La différence est déjà 100 fois ! Faites attention:le nombre d'éléments dans le tableau a augmenté de 100 fois (de 10 à 1000), et le nombre de vérifications nécessaires pour la recherche binaire n'a augmenté que de 2,5 fois - de 4 à 10. Si nous atteignons 10 000 éléments , la différence est encore plus impressionnante : 10 000 vérifie la recherche linéaire et un total de 14 vérifications binaires. Et encore : le nombre d'éléments a été multiplié par 1 000 (de 10 à 10 000), mais le nombre de contrôles n'a augmenté que de 3,5 fois (de 4 à 14). La complexité de l'algorithme de recherche binaire est logarithmique ou, en notation Big-O, O(log n) . pourquoi c'est appelé comme ça? Un logarithme est l'inverse de l'exponentiation. Le logarithme binaire est utilisé pour calculer la puissance de 2. Par exemple, nous avons 10 000 éléments que nous devons parcourir à l’aide d’une recherche binaire. Vous avez désormais une image sous les yeux et vous savez que cela nécessite un maximum de 14 contrôles. Mais que se passe-t-il s'il n'y a pas d'image sous vos yeux et que vous devez compter le nombre exact de contrôles nécessaires ? Il suffit de répondre à une question simple : à quelle puissance faut-il élever le nombre 2 pour que le résultat obtenu soit >= le nombre d'éléments vérifiés ? Pour 10 000, ce sera la puissance 14. 2 à la puissance 13 est trop petit (8192) Mais 2 à la puissance 14 = 16384 , ce nombre satisfait notre condition (c'est >= le nombre d'éléments dans le tableau). Nous avons trouvé le logarithme - 14. C'est le nombre de contrôles dont nous avons besoin ! :) Les algorithmes et leur complexité sont un sujet trop vaste pour être inclus dans une seule conférence. Mais le savoir est très important : dans de nombreux entretiens, vous serez confronté à des problèmes algorithmiques. Pour la théorie, je peux vous recommander plusieurs livres. Un bon point de départ est « Grocking Algorithms » : bien que les exemples du livre soient écrits en Python, le langage et les exemples du livre sont très simples. La meilleure option pour un débutant, et elle est également de petit volume. Lectures plus sérieuses : livres de Robert Laforet et Robert Sedgwick . Les deux sont écrits en Java, ce qui vous facilitera un peu l’apprentissage. Après tout, vous connaissez bien ce langage ! :) Pour les étudiants ayant une bonne formation en mathématiques, la meilleure option serait le livre de Thomas Corman . Mais vous ne vous contenterez pas de la simple théorie ! « Know » != « be able » Vous pouvez vous entraîner à résoudre des problèmes d'algorithmes sur HackerRank et Leetcode . Les problèmes de là sont souvent utilisés même lors d'entretiens sur Google et Facebook, vous ne vous ennuierez donc certainement pas :) Pour renforcer le matériel de cours, je vous conseille de regarder une excellente vidéo sur Big-O sur YouTube. Rendez-vous aux prochaines conférences ! :)