Quelle est la complexité temporelle de l’algorithme ? Choisissez la borne la plus simple et la plus stricte possible.

Si vous deviez adapter cet algorithme (en gardant l'approche par force brute) pour identifier la somme maximale d'un quadruplet d'éléments, quelle serait la complexité temporelle de l’algorithme ? Choisissez la borne la plus simple et la plus stricte possible.

Comme vous le savez sûrement, il existe souvent des approches plus efficaces que l’approche par force brute. Proposez un algorithme paire_max_efficace qui résout le même problème que paire_max mais qui présente une complexité temporelle inférieure. Pour vous aider, vous pourriez commencer par imaginer la recherche de l’élément maximal et voir comment l’adapter à la recherche d’une paire de somme maximale. Attention, il vous est interdit d’utiliser un algorithme de tri.

Vous êtes chargés d'implémenter la fonction suivante en Python. Pour préparer votre code, vous pouvez télécharger le fichier paire_max_efficace.py qui contient la signature de la fonction et quelques exemples de tests.

Attention : seul le résultat renvoyé est évalué et non la complexité temporelle.

Note: Lorsqu'il vous est demandé d'implémenter une fonction, vous êtes invités à ne remplir que le corps de la fonction à implémenter.

def paire_max_efficace(a):
    """
    Calcule la somme maximale d'une paire d'entiers de `a`
    pre: `a` est un tableau (list) d'entiers
    pre: len(`a`) >= 2
    post: retourne la somme maximale obtenue à partir d'une
        paire d'entiers de `a`
    """

# A implémenter

Quelle est la complexité temporelle de l’algorithme que vous proposez (paire_max_efficace)? Choisissez la borne la plus simple et la plus stricte possible.