Salut! La leçon d'aujourd'hui sera légèrement différente des autres. Il diffère en ce qu'il n'est qu'indirectement lié à Java. Cela dit, ce sujet est très important pour chaque programmeur. Nous allons parler d' algorithmes . Qu'est-ce qu'un algorithme ? En termes simples, il s'agit d'une séquence d'actions qui doivent être complétées pour obtenir un résultat souhaité . Nous utilisons souvent des algorithmes dans la vie de tous les jours. Par exemple, chaque matin vous avez une tâche précise : aller à l'école ou au travail, et en même temps être :
- Habillé
- Faire le ménage
- nourris
- Réveillez-vous à l'aide d'un réveil.
- Prenez une douche et lavez-vous.
- Préparez le petit-déjeuner et du café ou du thé.
- Manger.
- Si vous n'avez pas repassé vos vêtements la veille au soir, repassez-les.
- S'habiller.
- Quitter la maison.
- Achetez ou téléchargez l'édition 1961 du troisième nouveau dictionnaire international de Webster.
- Trouvez tous les noms de notre liste dans ce dictionnaire.
- Sur une feuille de papier, écrivez la page du dictionnaire sur laquelle se trouve le nom.
- Utilisez les morceaux de papier pour trier les noms.
for
qui effectue cette tâche
int[] numbers = new int[100];
// ...fill the array with numbers
for (int i: numbers) {
System.out.println(i);
}
Quelle est la complexité de cet algorithme ? Linéaire, c'est-à-dire O(n). Le nombre d'actions que le programme doit effectuer dépend du nombre de numéros qui lui sont transmis. S'il y a 100 nombres dans le tableau, il y aura 100 actions (instructions pour afficher des chaînes à l'écran). S'il y a 10 000 nombres dans le tableau, alors 10 000 actions doivent être effectuées. Notre algorithme peut-il être amélioré de quelque manière que ce soit ? Non. Quoi qu'il en soit, nous devrons effectuer N passages dans le tableau et exécuter N instructions pour afficher les chaînes sur la console. Prenons 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 avons un vide LinkedList
dans lequel nous insérons plusieurs nombres. Nous devons évaluer la complexité algorithmique de l'insertion d'un seul numéro dans le LinkedList
dans notre exemple, et comment cela dépend du nombre d'éléments dans la liste. La réponse est O(1), c'est-à-dire une complexité constante . Pourquoi? Notez que nous insérons chaque numéro au début de la liste. De plus, vous vous souviendrez que lorsque vous insérez un nombre dans un LinkedList
, les éléments ne se déplacent nulle part. Les liens (ou références) sont mis à jour (si vous avez oublié comment fonctionne LinkedList, regardez une de nos anciennes leçons ). Si le premier nombre de notre liste est x
, et que nous insérons le nombre y au début de la liste, alors tout ce que nous devons faire est ceci :
x.previous = y;
y.previous = null;
y.next = x;
Lorsque nous mettons à jour les liens, nous ne nous soucions pas du nombre de chiffres déjà présents dans leLinkedList
, qu'il s'agisse d'un ou d'un milliard. La complexité de l'algorithme est constante, c'est-à-dire O(1).