Introduction à la complexité et sa formalisation

Étudiant : ALBRECHT Maël

Tuteur : HIRSCHOWITZ Tom

Introduction

Lorsque nous créons de grands programmes, l'optimisation de ceux-ci est importante pour diminuer le temps d'exécution et la longueur de ceux-ci. Pour cela, nous allons donc nous intéresser au principe de complexité.

Complexité

La complexité permet de mesurer l'efficacité des fonctions. La complexité dépend de différents critères tel que par exemple :

• le temps de calcul séquentiel , c'est a dire le temps qui es mis pour exécuter toute les instructions une par une.

• le temps de calcul parallèle , c'est a dire le temps qui es mis pour exécuter toute les instructions avec plusieurs processeur donc avec des opération exécuté en simultané.

• l'esapace disque nécessaire a ces opération qui peut donc ralonger le temps d'execution d'une opérations.

• ainsi que beaucoup d'autre paramètre...

Pour illustrer cela nous allons utiliser deux fonctions « identité » comme exemple.

On commence donc par définir un type d'entier unaires.

type nat = Z | S of nat
let one = S Z
let two = S (S Z) (* etc.. *)