Complexité en temps (Time complexity)

La complexité en temps permet de mesurer le temps requis pour l’exécution d’un algorithme en tenant compte de l’augmentation des données (data).

Pour représenter le temps d’exécution nous utilisons le big O notation.

Constant (Constant time)

Exemple :

func printFirstAge(ages: [Int]) {
    if let age = ages.first {
        print(age)
    } else {
        print("Error")
    }
}

 

Un algorithme constant time détient toujours le même temps d’exécution sans prendre  en compte la taille de la data. La big O notation pour la constant time est O(1).

Linéaire (Linear time)

Exemple :

func printAges(ages: [Int]) {
    for age in ages {
        print(ages)
    }
}

La fonction printFirstAge a pour objectif d’afficher tout les integers du tableau.

Un algorithme linéaire voit son temps d’exécution augmenter du même montant que l’augmentation de la taille de la data. La big O notation pour le linéaire est O(n). Point important si vous parcourez un tableau de taille 6, nous allons simplifier à 0(n) est non pas à O(6).

Logarithmique (Logarithmic time)

Il est probablement plus complexe que les autres cependant il est très intérèssant au niveau des performances et permet d’éviter dans certains cas l’utilisation d’un algorithme linéaire afin d’obtenir un temps d’exécution plus court.

L’exemple le plus parlant est la Recherche dichotomique (Binary search). la Recherche dichotomique est un algorithme qui permet de trouver un élément dans un tableau trié. Cet algorithme utilise un temps d’exécution Logarithmique. Dans le cas de la Binary search l’erreur aurait été de parcourir chacun des éléments d’un tableau afin de trouver l’élément recherché. Nous aurions alors utilisé un time complexity Linéaire est donc plus couteux.

Pour un graphique plus précis cliquer ici.

La big O notation pour le logarithmique est O(log n)

Quadratique (Quadratic time)

Exemple :

func printAges(ages: [Int]) {
    for _ in ages {
        for age in ages {
            print(age)
        }
    }
}

Comme vous le constatez si nous avons 3 ages (5, 29, 33), la console affichera 9 print statements (n²).

5
29
33
5
29
33
5
29
33

A savoir qu’un algorithme linéaire sera toujours plus performant en temps d’execution qu’un algorithme quadratique même si il est optimisé. La big O notation pour le quadratique est O(n²).


Il existe de nombreux autres time complexities. Vous pouvez en avoir un aperçu ici.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *