[TP.02] Complexité calculatoire - Mystère - [LINFO1103] Introduction à l'algorithmique

On s'intéresse à l'algorithme Mystère décrit dans le pseudo-code ci-dessous.

Paste this command into your terminal:

The password to connect is

Please answer to all the questions. Εσωτερικό σφάλμα {} has not a valid extension. {} is too heavy.

Que renvoie l'algorithme lorsqu'il est appelé avec la valeur $n=3$ passée en paramètre ?

De façon générale, que renvoie l'algorithme lorsqu'il est appelé avec un paramètre $n$ quelconque (mais entier et strictement positif) ?

$\sum_{i=1}^{n}(i+1)$

${n^n}^{n/2}$

Autre chose

$n^2*\frac{n}{2}$

$\sum_{i=1}^{n}(\sum_{j=1}^{n}(i+1))$

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

$O(n^3)$

$\Omega(n^2*n)$

$\Theta(n^2+n)$

$\Theta(n^3)$

$\Omega(n^2+n)$

Trouvez, si possible, un algorithme qui résout le même problème avec une complexité temporelle en $\Theta(n)$ ou $\Theta(1)$ .

Vous êtes chargés d'implémenter la fonction suivante en Python.

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 mystere(n):
    '''
    pre: `n` > 0
    post: ???
    '''

# A implémenter

 
# A implémenter

Author(s)	Vincent Branders, Pierre Dupont
Deadline	26/02/2025 14:00:00
Submission limit	No limitation

[TP.02] Complexité calculatoire - Mystère