Différence entre la complexité temporelle et la complexité informatique

Pour mesurer la complexité d'un algorithme, s'agit-il d'une complexité temporelle ou d'une complexité informatique? Quelle est la différence entre eux?

J'ai utilisé pour calculer le nombre maximal (pire) d'opérations de base (les plus coûteuses) dans l'algorithme.

La complexité informatique n'est qu'un terme plus général, car le temps n'est pas la seule ressource à considérer. Le deuxième plus évident est l'espace utilisé par un algorithme, et donc nous pouvons parler d' espace complexité de l' , également en tant que partie de la complexité de calcul. En effet, nous pouvons le faire pour toute mesure que vous vous souciez d'utiliser, bien sûr, certaines mesures sont plus utiles que d'autres.

Donc, compter le nombre de pas qu'un algorithme prend dans le pire des cas donne une complexité temporelle liée au problème qu'il résout, compter la quantité de mémoire / le nombre de cellules de bande qu'il utilise donne une complexité d'espace liée, etc. etc.

Rappelez-vous également que si vous voulez être strict, la complexité fait référence au problème, pas à l'algorithme, donc un problème a des limites de complexité, un algorithme a des limites de ressources (temps d'exécution, utilisation de l'espace ...). C'est juste une question de formalité définitionnelle, la théorie de la complexité traite des problèmes. Oui, les algorithmes sont un outil clé pour analyser les problèmes et la complexité et l'algorithmique est étroitement liée, mais formellement, nous ne dirions pas que Merge-Sort (un algorithme) est en , c'est le problème S o r t i n g qui est en P . Merge-Sort utilise certaines ressources ( O ( n log n $P$$\mathsf{Sorting}$$P$$O(n\log n)$par exemple). La limite de ressource et l'exactitude de l'algorithme impliquent la complexité (supérieure) du problème, mais ce sont des choses différentes. est également T C 0 -complete sous A C 0 -réductions, cette complexité liée ne peut vraiment être déclaré pour un problème (mais a des implications algorithmiques).$\mathsf{Sorting}$$TC^{0}$$AC^{0}$

La complexité cyclomatique est souvent utilisée comme mesure de la complexité de calcul, un exemple utile est fourni dans /programming/9097987/calculation-of-cyclomatic-complexity

Il peut y avoir de nombreux chemins différents (éventuellement imbriqués) à travers un algorithme lui conférant une complexité cyclomatique élevée, mais pas de boucles lui donnant une faible complexité temporelle. Un programme avec une seule boucle aurait une faible complexité cyclomatique mais peut-être une complexité temporelle élevée.

La complexité cyclomatique est souvent utilisée comme mesure de la maintenance requise pour le code. Une discussion plus détaillée est fournie dans http://docs.sonarqube.org/display/SONAR/Bad+Distribution+of+Complexity . Ceci est différent de la complexité temporelle qui est la mesure du temps d'exécution du code et peut être utilisée pour évaluer la perception des utilisateurs de l'efficacité du système.