tc_info:2020_cpp_6-3

Différences

Ci-dessous, les différences entre deux révisions de la page.

Lien vers cette vue comparative

tc_info:2020_cpp_6-3 [2020/09/30 15:47] – créée ppreatc_info:2020_cpp_6-3 [2020/09/30 15:47] (Version actuelle) – pprea
Ligne 1: Ligne 1:
 +Quand on écrit $L[1: -1]$, on effectue une recopie de la partie "centrale "de la liste, qui prend un temps $O(n)$. 
  
 +La relation de récurrence est donc $t(n) = n + t(n-2)$, & l'algorithme en $O(n^2)$.
 +
 +Il est possible d'éviter la recopie & donc de l'écrire en $O(n)$. [[2020_cpp-6-4|Solution(correcte)]]