[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.

Dán dòng lệnh này vào terminal của bạn:

Mật khẩu để kết nối là

Xin hãy trả lời tất cả các câu hỏi. Lỗi nội tại hệ thống {} 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) ?

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

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

Autre chose

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

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

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

$\Theta(n^2+n)$

$\Theta(n^3)$

$O(n^3)$

$\Omega(n^2+n)$

$\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

Tác giả	Vincent Branders, Pierre Dupont
Hạn chót	26/02/2025 14:00:00
Giới hạn nộp bài	Không có giới hạn

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