Bonjour à tous. Alors après plusieurs recherches infructueuses, je me tourne vers vous afin d'obtenir une définition de la complexité (en java notamment). Pourriez-vous m'aider s'il vous plaît?

Merci

La complexité algorithmique ?

Yep

Je peux proposer une petite introduction informelle mais je précise que je ne m'y connais pas, d'autre pourront mieux en parler que moi, et je n'aborderais pas les mathématiques derrière sauf si c'est ce que tu recherches.

Déjà c'est pas spécifique à un langage alors je vois pas trop pourquoi tu dis "en Java notamment".
Mais j'imagine que ce qui t'intéresses c'est l'analyse de la complexité algorithmique.

Le but c'est d'évaluer l'efficacité d'un algorithme et pour ça on évalue son ordre de grandeur en nombre d'opérations.
On pourrait évaluer les algorithmes par le temps d'exécution mais on se rend compte que c'est pas assez fiable vu que le temps d'exécution d'un programme dépend de nombreux facteurs dont le microprocesseur, le compilateur, l'ordinateur sur lequel le programme tourne etc.

Donc on compte le nombre d'opérations de l'algorithme. Et ce nombre d'opérations doit s'exprimer en fonction de une ou plusieurs variables.

Par exemple, on a tab un tableau de chaînes de caractères de taille n. Et la fonction suivante d'affichage des éléments :

public void afficher(ArrayList<String> tab){
    for (String s : tab)
        System.out.println(s);
}

La structure de contrôle "for" ne compte pas comme une opération. On a donc une seule opération qui s'exécute autant de fois qu'il y a d'éléments dans le tableau. Le tableau est de taille n donc on a n opérations.

On dit que cet algorithme est de complexité linéaire en O(n).
Si ton nombre d'opération est un polynôme comme n²+2n+1 par exemple, il faut prendre le terme dominant, la complexité est donc polynomiale en O(n²).
Pour la recherche dans un tableau on ne se préoccupe pas de la position de l'élément à rechercher, on considère toujours le "pire des cas" donc que l'élément recherché est à la fin du tableau. Si un algorithme est de complexité O(n) cela veut dire que n est le nombre maximal d'opérations que l'algorithme effectue.
Ensuite il y a de nombreux types de complexité.

Sinon je ne vois pas pourquoi tes recherches n'ont pas été fructueuses il y a beaucoup de choses sur Internet et pour les mathématiques derrière il faut des notions d'analyse (notations de Landau).
Ensuite il y a aussi les classes de complexité mais il faut avoir certaines notions en calculabilité par exemple.