Bonjour,

j'ai besoin de votre aide pour comprendre la complexité en temps et en espace d'une fonction en c car depuis 2 ans je le fais mais je ne comprend rien.

Merci beaucoup.

La complexcité, quelque soit le langage, est quelque chose d'assez ardue à apréhender. Je serais incapable de l'expliqué par moi-même, donc je t'invite à regarder ce cours. En éspérant que cela puisse t'aider. Il faut certaines notions de maths (logarithme, exponentielle, puissance et factorielle) et aussi savoir ce que sont que le heap (ou "tas" en français) et la stack (ou "pile" en français). Bon courage

Grosso modo l'idée générale est d'exprimer le temps d'exécution (ou l'espace mémoire que ça prend) à partir d'une "taille" d'entrée.

Qu'est ce que c'est qu'une "taille d'entrée" ? C'est difficile de donner une règle générale mais on peut donner quelques exemples :

• Si tu fais une fonction qui te trie un tableau, ta taille d'entrée pourrait être la longueur du tableau
• Si tu codes un jeu vidéo et que tu fais un matchmaking (regrouper les joueurs qui veulent jouer en plusieurs match), la taille d'entrée pourrait être le nombre de joueurs
• Si tu fais un algo sur des réseaux sociaux style Facebook, où chaque personne est "reliée" à d'autres personnes en suivant un graphe, tu pourrais avoir deux tailles d'entrée : le nombre de noeuds du graphe (le nombre de personne), et le nombre de liaisons du graphe (le nombre de relation ami qu'on la totalité des personnes)

Etant donné donc une taille N, et étant donné une fonction t(N) qui te donne le temps d'exécution de ta fonction en fonction de la taille (tu ne connais pas cette fonction), tu cherches à connaitre l'allure de la fonction, comment elle varie

Pour une fonction linéaire (c'est à dire t(N) = k*N), on dit que ça varie en O(N). La notation O en math a une signification bien précise - en informatique ça veut juste dire "ça varie comme une fonction N -> k*N".

Quand tu as une complexité linéaire en O(N), si tu doubles ta taille d'entrée, tu doubles aussi le temps d'exécution. Par exemple si t(N) = k*N, t(2N) = k*2N = 2*t(N). Afficher les valeurs d'un tableau est une fonction de complexité linéaire : si tu as un tableau deux fois plus grand, tu prendras deux fois plus de temps à l'afficher.

Quand tu as une complexité quadratique en O(N²), doubler la taille d'entrée revient à quadrupler le temps d'exécution. Par exemple, si t(N) = k*N², t(2N) = k*4N² = 4*t(N). Un exemple d'algorithme quadratique : trier les valeurs d'un tableau par insertion (à chaque tour de boucle tu prends le max et tu le mets dans un tableau).

Il existe des algorithmes de complexité exponentielle en O(2^N). Dans ce cas, si tu incrémentes la taille d'entrée, tu doubles le temps d'exécution. Si t(N) = k*2^N, t(N+1) = k*2^(N+1) = 2 * k * 2^N = 2 * t(N). Il y a pas mal de problèmes en informatiques dont la résolution est en temps exponentiel, par exemple le problème du voyageur de commerce.

Il est difficile de déterminer des règles précises pour évaluer la complexité d'un programme. Mathématiquement, la complexité d'un programme c'est la somme de la complexité des instructions exécutées.. Par exemple :

for i from 1 to N do
  print "Coucou"
done

Si tu supposes que le "print coucou" est de complexité O(1) (c'est à dire un coût constant qui ne dépend pas de N), le coût temporel d'exécution de cette boucle, c'est la somme de 1 à N de O(1), c'est à dire O(1)+O(1)+..+O(1), N fois, c'est à dire O(N).

Si tu supposes maintenant que tu as une double boucle 

for i from 1 to N do
  for j from 1 to N do
    print "Coucou"
  done
done

La complexité de ce truc là, c'est la somme de la somme de O(1), N fois. La somme de O(1) N fois c'est O(N), donc ce qu'on calcule c'est O(N) + O(N) + ... + O(N), N fois, c'est à dire O(N²).

Pour la complexité spatiale : c'est pareil, mais on cherche maintenant à exprimer la taille de l'empreinte mémoire de la fonction. Par exemple si ta fonction utilises un tableau de taille N, alors la complexité mémoire sera O(N). Il existe des algos qui ont une complexité temporelle O(N), mais une complexité mémoire O(2^N). Typiquement si tu fais de la mémoïsation (je te laisse chercher en quoi ça consiste), tu diminues ta complexité temporelle mais tu augmentes ta complexité mémoire..

Voilà j'espère que ça t'aide un peu. Pour la complexité temporelle, si t'as que des boucles for c'est très facile à déterminer. Si t'as des boucles while il faut te poser la question "Combien d'itération vais-je faire au pire cas ?", sachant qu'on peut aussi regarder le cas moyen mais c'est plus compliqué. Si t'as des fonctions récursives, là faut prendre du recul et se demander combien d'appel récursif tu vas faire.

Des fois c'est quasi impossible de donner une complexité très précise. C'est pour ça que les calculs de complexité ont l'air d'être un peu de "pifomètre" - il faut réussir à voir l'algo dans son ensemble et voir grosso modo comment ça se comporte, ce qui n'est pas évident.

Expérimentalement tu peux tester la complexité temporelle assez facilement en essayant différentes tailles de données, et en regardant comment ton temps évolue.