Merci de changer vos notes de TP ainsi que l’exercice 5 du TD2 en cette version :
def fusion(L1:list,L2:list) -> list:
''' Entrée : deux listes triées
Sortie : leur fusion en une liste triée '''
n, m = len(L1), len(L2)
if n == 0: return L2
if m == 0: return L1
if L1[n-1] >= L2[m-1]:
R = fusion(L1[0:n-1], L2)
R.append(L1[n-1])
return R
else:
R = fusion(L1, L2[0:m-1])
R.append(L2[m-1])
return REn effet, dans la précédente je faisais les fusions [L1[0]] + fusion(…, …) pour faire comme des append mais à gauche, mais cette concaténation est en O(n+m) ce qui rendait fusion quadratique et non pas linéaire. Comme append est en O(1), cette version ci-dessus est bien linéaire.
(Pour les optionnaires : j’ai pensé en oCaml, pour lequel les append se font à gauche avec le constructeur de liste :: )
Par ailleurs, j’ai mis un corrigé du TP9 en ligne.
