Différences

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

--- tc_info:2020_cpp_6-3 [2020/09/30 15:47] – créée pprea
+++ tc_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)]]