Complexité temporelle

[invite5d1ec8ab]

Bonsoir,
Est-ce que quelqu'un pourrait m'expliquer de manière simple svp ce qu'est la complexité temporelle? Plus précisément, me dire comment on fait pour la calculer (avec un exemple pas trop simple).

Merci.
-----

[geometrodynamics_of_QFT]

avec un exemple pas trop simple, ça va être dur pour toi de comprendre

intuitivement...je dirais que c'est la quantité de temps de processeur nécéssaire, en relation avec la dimension N du problème considéré.
un processeur à 1GHz fait 1 milliard d'opérations de base (addition, multiplication, lecture mémoire, écriture..) par seconde

par exemple, l'algorithme consistant à additionner les valeurs d'un tableau de N entrées, est en O(N), car il faut autant d'opérations que de valeurs.
un algorithme qui consiste à déterminer la taille d'un tableau, sera aussi en O(N), car il va parcourir naivement toutes les entrées jusqu'à la dernière.

si tu crées un objet contenant une liste de valeurs, ainsi qu'une variable mise à jour chaque fois que tu modifies la liste, et qui comptabilise le nombre d'éléments dans la liste,
alors la fonction int get_length() { return objet_liste.length } sera en O(1)=O(N^0), indépendante de la taille de la liste (puisqu'une variable est mise à jour à chaque modification)

un algorithme qui consiste à trier un tableau, sera en O(x)>O(N), car il faut parcourir le tableau plusieurs fois en fonction des algorithmes utilisés (tri sélectif, aléatoire, etc..)


en résumé : complexité temporelle d'un algorithme en O( nombre d'éléments à traiter * nombre d'opérations par "traitement") = O(nombre d'opération total)

[geometrodynamics_of_QFT]

par exemple, l'algorithme consistant à additionner les valeurs d'un tableau de N entrées, est en O(N), car il faut autant d'opérations que de valeurs.

Il va ensuite écrire cette somme dans un endroit de la mémoire pour qu'une variable puisse y accéder, mais cette opération est unique, peu importe la taille du tableau : est elle est en O(N^0)=O(1).
Donc la complexité globale de l'algorithme est O(N) (la plus contraignante en temps)