Exercice 2 - Coût des algorithmes · Bac Numérique et Sciences Informatiques Nouvelle-Calédonie 2023 (jour 2)

Exercice 2 (4 points)

Tous les programmes de cet exercice seront écrits en langage Python.

1) Un mot est un palindrome lorsqu'il s'écrit de la même façon à l'endroit et à l'envers.

Exemples: radar, abcdcba, kayak, laval, non, ressasser, elle.

Soit la fonction ci-dessous appelée palindrome.

def palindrome(mot):

n=len(mot)

est_palindrome=True

for k in range(n//2):

if mot[k]!=mot[n-k-1]:

est_palindrome=False

return est_palindrome

b)

Indiquer sans justification la complexité en temps de calcul de cet algorithme pour un mot de longueur $n$.

Remarque: on ne comptera que les comparaisons de caractères.