Algorithme " La complexité "

Ah d'accord je vois merci , Oui c'est comme par exemple le Tri par comptage qui requiert un for imbriqué mais dont sa complexité est exprimé en O(n) , Justement c'est l'une des difficultés que j'éprouve lorsque je suis confronté à un Algorithme , Par exemple y'a certaines méthodes que j'essaie de résoudre mais je n'arrive pas a me posé les bonnes questions et pouvoir déterminé si j'aurais besoins d'une boucle ou plus ce qui m’empêche de codé.

C'est vraiment du cas par cas. Il n'y a que l'habitude qui te permettra de faire les bons choix, mais dans les programmes "de la vraie vie" c'est à 90% des traitements en O(n) malgré des boucles imbriquées liée à la structure objet.

Exemple :

List<List<List<String>>> list1 = ...;
for (List<List<String>> list2 : list1)
     for (List<String> list3 : list2)
          for (String str : list1)
               f(str);

La complexité s'exprimant sur f() est en O(n) car on appelle une seule fois chacun des String malgré les 3 boucles for qu'il est nécessaire de parcourir pour décomposer la structure objet initiale afin de traiter tous les String voulus.

Ahh d'accord j'vois un peut plus clair a présent Merci donc supposons que maintenant nous avons :

List<List<List<String>>> list1 = ...;
for (List<List<String>> list2 : list1)
     for (List<String> list2 : list3)
          for (String str : list1)
               f(str); 

Dans ce cas puis-je en conclure que la complexité de cet Algorithme est exprimé en O(n^2) car j'Utilise plus d'une fois list2 ?

Ce code ne compilerai pas donc je ne sais pas exactement ce que tu voudrais en faire.

Un exemple de O(n²) serait l'utilisation d'un f() à deux paramètres ayant chacun un élément de la liste.

List<String> list = ...;
for (String str1 : list)
    for (String str2 : list)
        f(str1, str2)

Ici on peut voir ça comme un tableau, avec les éléments de la liste en colonne et les mêmes éléments de la même liste en ligne, donc les résultats f() sont inscrits sur chaque case de ce tableau, et sont donc beaucoup plus nombreux que lors de l'exemple précédent dont les appels à f() ne se faisaient que sur une dimension, en ligne.

Ahh d'accord et Donc par Exemple supposons que nous venons a manipuler des Tableaux multidimensionnels , pourraient t-ont considéré que la complexité est de l'Ordre O(n²) ?