Vidéo: test psychotechnique grille corrigé 1 2024
Plus un algorithme a besoin d'opérations, plus il est complexe. La complexité est une mesure de l'efficacité de l'algorithme en termes d'utilisation du temps, car chaque opération prend du temps. Étant donné le même problème, les algorithmes complexes sont généralement moins favorables que les algorithmes simples, car les algorithmes complexes nécessitent plus de temps.
Pensez aux moments où la rapidité d'exécution fait la différence, comme dans le secteur médical ou financier, ou lorsque vous pilotez en mode automatique sur un avion ou une fusée spatiale. Mesurer la complexité de l'algorithme est une tâche difficile, bien que nécessaire si vous voulez utiliser la bonne solution. La première technique de mesure utilise des machines abstraites comme la Random Access Machine (RAM).
RAM est également synonyme de Random-Access Memory, qui est la mémoire interne utilisée par votre ordinateur lors de l'exécution de programmes. Même si elle utilise le même acronyme, une machine à accès aléatoire est quelque chose de complètement différent.
Les machines abstraites ne sont pas de vrais ordinateurs, mais des machines théoriques, des ordinateurs qui sont imaginés dans leur fonctionnement. Vous utilisez des machines abstraites pour considérer comment un algorithme fonctionnerait sur un ordinateur sans le tester sur le réel, mais lié par le type de matériel que vous utiliseriez. Un ordinateur RAM effectue des opérations arithmétiques de base et interagit avec des informations en mémoire, c'est tout. Chaque fois qu'un ordinateur RAM fait quelque chose, cela prend un pas de temps (une unité de temps). Lorsque vous évaluez un algorithme dans une simulation RAM, vous comptez les pas de temps en suivant la procédure suivante:
- Comptez chaque opération simple (opérations arithmétiques) comme un pas de temps.
- Divisez les opérations complexes en opérations arithmétiques simples et comptez les pas de temps définis à l'étape 1.
- Comptez tous les accès aux données de la mémoire comme un pas de temps.
Pour effectuer cette comptabilisation, vous écrivez une version pseudo-code de votre algorithme et exécutez ces étapes en utilisant du papier et un crayon. En fin de compte, c'est une approche simple basée sur une idée de base du fonctionnement des ordinateurs, une approximation utile que vous pouvez utiliser pour comparer des solutions indépendamment de la puissance et de la vitesse de votre matériel ou du langage de programmation que vous utilisez.
L'utilisation d'une simulation est différente de l'exécution de l'algorithme sur un ordinateur car vous utilisez une entrée standard et prédéfinie. Les mesures réelles sur ordinateur exigent que vous exécutiez le code et que vous vérifiiez le temps requis pour l'exécuter. L'exécution de code sur un ordinateur est en fait un benchmark, une autre forme de mesure de l'efficacité, dans laquelle vous tenez également compte de l'environnement de l'application (tel que le type de matériel utilisé et l'implémentation du logiciel).Un benchmark est utile mais manque de généralisation. Considérez, par exemple, comment un nouveau matériel peut rapidement exécuter un algorithme qui a pris un certain temps sur votre ancien ordinateur.
