Formateur_complexite_py.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "hrNWtB2pgZv2"
   },
   "source": [
    "# Complexités en temps et en espace."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Table des matières\n",
    "**[Chapitre 0 - Introduction](#M0)** \n",
    "- [1. Contexte](#M01)\n",
    "- [2. Problématique](#M02) \n",
    "- [3. Exemple](#M03) \n",
    "\n",
    "**[Chapitre 1 - La complexité](#M1)**  \n",
    "- [1. Première définition](#M11)\n",
    "- [2. Comparons deux algorithmes](#M12) \n",
    "- [3. Évaluation de la complexité algorithmique](#M13) \n",
    "- [4. Seconde définition](#M14) \n",
    " \n",
    "**[Chapitre 2 - Premiers calculs de complexité : algorithmes itératifs](#M2)**.   \n",
    "- [1. Algorithmes sans structures de contrôle](#M21)  \n",
    "- [2. Le cas des structures conditionnelles](#M22)  \n",
    "- [3. Le cas des structures itératives](#M23) \n",
    "- [(Exercice 1) au programme de première NSI : tri par sélection](#M24)\n",
    "- [(Exercice 2) au programme de première NSI : tri par insertion](#M25)\n",
    "\n",
    "**[Chapitre 3 - Cas des algorithmes récursifs](#M3)**  \n",
    "- [1. Récursivités simples](#M31) \n",
    "- [2. Suites arithmético-géométriques](#M32)  \n",
    "- [3. Algorithmes de type \"diviser pour régner\" : exemple du tri fusion](#M33)\n",
    "- [(Exercice 3) Implémentation du tri fusion](#M34)\n",
    "\n",
    "**[Chapitre 4 - Un problème de dichotimie](#M4)**  \n",
    "- [(Exercice 4) Question 1](#M41) \n",
    "- [(Exercice 4) Question 2](#M42) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <font color=#3876C2> Chapitre 0 - Introduction</font> <a name=\"M0\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <font color=#FEB229> 1. Contexte</font> <a name=\"M01\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "ScIt_q9Ygzqt"
   },
   "source": [
    "un problème à résoudre\n",
    "\n",
    "- un problème = une question + des paramètres (données \"en entrée\")\n",
    "\n",
    "une instance de ce problème qui admet au moins une solution\n",
    "\n",
    "- une instance = un choix des données d'entrée\n",
    "\n",
    "un algorithme qui calcule sa solution\n",
    "\n",
    "- un ou même plusieurs algorithmes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <font color=#FEB229> 2. Problématique</font> <a name=\"M02\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "lvqrh0ECg98V"
   },
   "source": [
    "De combien de temps a besoin l'algorithme pour calculer cette solution ?\n",
    "\n",
    "De combien d'espace-mémoire a besoin l'algorithme pour calculer cette\n",
    "solution ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <font color=#FEB229> 3. Exemple</font> <a name=\"M03\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "GYBC-dIHh9mv"
   },
   "source": [
    "On veut calculer la somme de *n* entiers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "8YjfnZvxiJjD"
   },
   "source": [
    "**Une instance :**\n",
    "un choix de n et des n valeurs du tableau t\n",
    "\n",
    "**Principe d'un algorithme :**\n",
    "je parcours le tableau, \"du début à la fin\", je lis\n",
    "chaque valeur, je l'accumule dans une variable (initialement mise à zéro),\n",
    "je retourne cette variable."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "collapsed": true,
    "id": "5vSRe3y8iXP7"
   },
   "outputs": [],
   "source": [
    "def sommer(t, dim_t):\n",
    "    ''' somme itérative de n=dim_t valeurs entières stockées dans une liste t\n",
    "    entrées. t liste d’int de longueur dim_t\n",
    "    retourne. res int'''\n",
    "    res = 0 # j’'accumule dans res\n",
    "    for i in range(dim_t):\n",
    "        res = res + t[i]\n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "collapsed": false,
    "id": "mtZjhD3Diols",
    "outputId": "f861d40f-01d7-42ac-b4d6-254721c72f04"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "23\n"
     ]
    }
   ],
   "source": [
    "print(sommer([2,5,7,9],4))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "OmMRaxTN8FF2"
   },
   "source": [
    "**Combien de temps pour calculer la réponse ?**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "collapsed": false,
    "id": "ZiuTAYmpGfSf",
    "outputId": "5c3f5e1c-1783-4aa8-f042-325792e20293"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The slowest run took 5.34 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "1000000 loops, best of 3: 691 ns per loop\n"
     ]
    }
   ],
   "source": [
    "%timeit sommer([2,5,7,9],4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "dKmtLO4Q8LeA"
   },
   "source": [
    "- ça dépend de n : le nombre de valeurs à sommer\n",
    "- A priori, le temps de calcul est une fonction croissante de n\n",
    "- Oui mais croissante comment ? linéaire ? quadratique ?  logarithmique ?\n",
    "- On parle aussi de *coût* de l'algorithme"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "z346mcoe8kmn"
   },
   "source": [
    "**Combien d'espace-mémoire pour calculer la réponse ?**\n",
    "- ça dépend aussi de n : il faut déjà réussir à stocker les n valeurs !\n",
    "- Oui mais quel est l'espace mémoire supplémentaire pour résoudre le problème ?\n",
    "- Dépendant ou indépendant de n ? dépendant comment ? \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <font color=#3876C2> Chapitre 1 - La complexité</font> <a name=\"M1\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "O0P2Zd1qwYvO"
   },
   "source": [
    "### <font color=#FEB229> 1. Première définition</font> <a name=\"M11\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "LEp0elu9welN"
   },
   "source": [
    "Déterminer la complexité (ou le *coût*) d’un algorithme, c’est évaluer les ressources nécessaires à son exécution (essentiellement la quantité de mémoire requise) et le temps de calcul à prévoir. Ces deux notions dépendent de nombreux paramètres matériels qui sortent du domaine de l’algorithmique : nous ne pouvons attribuer une valeur absolue ni à la quantité de mémoire requise ni au temps d’exécution d’un algorithme donné. En revanche, il est souvent possible d’évaluer l’ordre de grandeur de ces deux quantités de manière à identifier l’algorithme le plus efficace au sein d’un ensemble d’algorithmes résolvant le même problème."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "FMdMBcaMxmpA"
   },
   "source": [
    "### <font color=#FEB229> 2. Comparons deux algorithmes</font> <a name=\"M12\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "nHnLMGa6xuab"
   },
   "source": [
    "La détermination du nombre de diviseurs d’un entier naturel n. Une première solution consiste à essayer si chacun des entiers compris entre 1 et n est un diviseur de n. Ceci conduit à définir la fonction diviseurs1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "collapsed": true,
    "id": "8fFmqRKRx_hi"
   },
   "outputs": [],
   "source": [
    "def diviseurs1(n) :\n",
    "    d = 0\n",
    "    k = 1\n",
    "    while k <= n :\n",
    "        if n % k == 0:\n",
    "            d +=1\n",
    "        k +=1\n",
    "    return d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "collapsed": false,
    "id": "xHDNzVNLzBLZ",
    "outputId": "47420796-90b6-4b15-f43e-d25cd6da8ef3"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n"
     ]
    }
   ],
   "source": [
    "print(diviseurs1(85))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "collapsed": false,
    "id": "LrYyW-7LyvhO",
    "outputId": "feb9ac37-cce3-4d7f-eb61-48d5323b9e07"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The slowest run took 4.91 times longer than the fastest. This could mean that an intermediate result is being cached.\n",
      "100000 loops, best of 3: 7.75 µs per loop\n"
     ]
    }
   ],
   "source": [
    "%timeit diviseurs1(85)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "V66QcGgrzaO-"
   },
   "source": [
    "Mais on peut aussi se faire la réflexion suivante :$$ si \\: d  \\in % \n",
    "[\\![  1~;~ p ]\\!]  \\:divise \\: n \\: alors \\: d′= \\frac{n}{d} \\: aussi ; de \\: plus,\\: d \\le \\sqrt{n}\\iff d′\\ge \\sqrt{n}. $$Autrement dit, il suffit de rechercher les diviseurs de n qui sont inférieurs ou égaux à$$\\sqrt{n}$$  pour en connaitre le nombre total : c’est le principe utilisé par la fonction diviseurs2 (on notera le traitement particulier réservé aux carrés parfaits)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "collapsed": true,
    "id": "k3PS2vB_mXKM"
   },
   "outputs": [],
   "source": [
    "def diviseurs2(n):\n",
    "    d = 0\n",
    "    k = 1\n",
    "    while k * k < n:\n",
    "        if n % k == 0:\n",
    "            d += 2\n",
    "        k += 1\n",
    "    if k * k == n:\n",
    "        d += 1\n",
    "    return d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "collapsed": false,
    "id": "WwU0iyb3mw2e",
    "outputId": "184d1846-f6d8-44fb-bccd-2b7a13b116fb"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n"
     ]
    }
   ],
   "source": [
    "print(diviseurs2(81))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "collapsed": false,
    "id": "1hl5ILJ1pSOx",
    "outputId": "d4014382-96a7-4ad0-ec01-9538c2776323"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1000000 loops, best of 3: 1.23 µs per loop\n"
     ]
    }
   ],
   "source": [
    "%timeit diviseurs2(85)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "aSb1oBZ1W_Sp"
   },
   "source": [
    "**Comment comparer ces deux versions ?** Si on se focalise sur les deux boucles conditionnelles de ces algorithmes\n",
    "on constate que dans les deux cas on effectue deux additions, une division euclidienne et un test. $$ Chacune \\: de\n",
    "\\: ces \\: opérations \\: est \\: effectuée \\: n \\: fois \\: dans \\: le \\: premier \\: cas, \\sqrt{n} \\: fois  \\: dans \\: le \\: second.$$ Nous ne connaissons pas le temps t1 nécessaire à la réalisation de ces différents calculs, mais on peut légitimement penser que le temps\n",
    "total d’execution de diviseurs1 n’est pas éloigné de $$ n*t1 + t2 $$, le temps t2 étant le temps requis par les autres opérations. De même, le temps requis par la fonction diviseurs2 est de l’ordre de $$ \\sqrt{n} * t1' + t2' $$\n",
    "Les temps t2 et t2'  sont négligeables pour de grandes valeurs de n ; de plus les valeurs de t1 et t1' importent peu ;\n",
    "elle dépendent de conditions matérielles qui nous échappent. Nous n’allons retenir que le taux de croissance de chacune de ces deux fonctions : proportionnel à n pour la première (on dira plus loin qu’il s’agit d’un algorithme\n",
    "de coût linéaire), proportionnel à  $$ \\sqrt{n} $$ pour la seconde. Autrement dit :\n",
    "\n",
    "– multiplier n par 100 multiplie le temps d’exécution de diviseurs1 par 100 ;\n",
    "\n",
    "– multiplier n par 100 multiplie le temps d’exécution de diviseurs2 par 10.\n",
    "\n",
    "Ainsi, connaissant le temps d’exécution pour une valeur donnée de n il est possible d’évaluer l’ordre de grandeur du temps d’exécution pour de plus grandes valeurs."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "A317vXCWdoZE"
   },
   "source": [
    "### <font color=#FEB229> 3. Évaluation de la complexité algorithmique</font> <a name=\"M13\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "iAIZeCsTdtfW"
   },
   "source": [
    "Pour réaliser l’évaluation de la complexité algorithmique, il est nécessaire de préciser un modèle de la technologie employée ; en ce qui nous concerne, il s’agira d’une machine à processeur unique pour laquelle les instructions seront exécutées l’une après l’autre, sans opération simultanées. Il faudra aussi préciser les instructions élémentaires disponibles ainsi que leurs coûts. Ceci est particulièrement important lorsqu’on utilise un langage de programmation tel que Python car ce langage possède de nombreuses instructions de haut niveau qu’il serait irréaliste de considérer comme ayant un coût constant : il existe par exemple une fonction *sort* qui permet de trier un tableau en une instruction, mais il serait illusoire de croire que son temps d’exécution est indépendant de la taille du tableau."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "kNZHoZQqeIAr"
   },
   "source": [
    "**La première étape** consiste donc à préciser quelles sont les instructions élémentaires, c’est-à-dire celle qui seront considérées comme ayant un coût constant, indépendant de leurs paramètres. Parmi celles-ci figurent en général :\n",
    "\n",
    "– les opérations arithmétiques (addition, soustraction, multiplication, division, modulo, partie entière, . . .)\n",
    "\n",
    "– la comparaisons de données (relation d’égalité, d’infériorité, . . .)\n",
    "\n",
    "– le transferts de données (lecture et écriture dans un emplacement mémoire)\n",
    "\n",
    "– les instructions\n",
    "\n",
    "Mais il y a des exceptions, par exemple la comparaison entre deux chaînes de caractères ne pourra être considérée comme une opération\n",
    "élémentaire, même s’il est possible de la réaliser en une seule instruction Python."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "J2X6W0XjilGO"
   },
   "source": [
    "Une fois précisé la notion d’opération élémentaire, il convient de définir ce qu’on appelle **la taille de l’entrée**.\n",
    "Cette notion dépend du problème étudié : pour de nombreux problèmes, il peut s’agir du nombre d’éléments constituant les paramètres de l’algorithme (par exemple le nombre d’éléments du tableau dans le cas d’un algorithme de tri) ; dans le cas d’algorithmes de nature arithmétique  il peut s’agir d’un entier passé en paramètre, voire du nombre de bits nécessaire à la représentation de ce dernier. Enfin, il peut être approprié de décrire la taille de l’entrée à l’aide de deux entiers (le nombre de sommets et le nombre d’arêtes dans le cas d’un algorithme portant sur les graphes)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Imaginons par exemple que l'on effectue une recherche séquentielle d’un élément dans une liste non triée. Le principe de l'algorithme est simple, on parcourt un par un les éléments jusqu'à trouver, ou pas, celui recherché. Ce parcours peut s’arrêter dès le début si le premier élément est \"le bon\". Mais on peut également être amené à parcourir la liste en entier si l’élément cherché est en dernière position, ou même n'y figure pas. Le nombre d'opération élémentaires effectuées dépend donc non seulement de la taille de la liste, mais également de la répartition de ses valeurs.\n",
    "\n",
    "Cette remarque nous conduit à préciser un peu notre définition de la complexité en temps. En toute rigueur, on devra en effet distinguer trois formes de complexité en temps :\n",
    "\n",
    "* **la complexité dans le meilleur des cas** : c'est la situation la plus favorable, qui correspond par exemple à la recherche d'un élément situé à la première postion d'une liste, ou encore au tri d'une liste déjà triée.\n",
    "\n",
    "* **la complexité dans le pire des cas** : c'est la situation la plus défavorable, qui correspond par exemple à la recherche d'un élément dans une liste alors qu'il n'y figure pas, ou encore au tri par ordre croissant d'une liste triée par ordre décroissant.\n",
    "\n",
    "* **la complexité en moyenne** : on suppose là que les données sont réparties selon une certaine loi de probabilités.\n",
    "\n",
    "On calculera le plus souvent la complexité dans le pire des cas, car elle est la plus pertinente. Il vaut mieux en effet toujours envisager le pire."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "yoAoeH9tjCkW"
   },
   "source": [
    "Une fois la taille n de l’entrée définie, il reste à évaluer en fonction de celle-ci le nombre T(n) d’opérations élémentaires requises par l’algorithme. Mais même s’il est parfois possible d’en déterminer le nombre exact, on se contentera le plus souvent d’en donner l’ordre de grandeur à l’aide des **notations de Landau**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "SMafzk-AkFBp"
   },
   "source": [
    "![Comparaisons asymptotiques](http://misterned.org/images/landau.PNG)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <font color=#FEB229> 4. Seconde définition</font> <a name=\"M14\"></a>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "\n",
       "<style>\n",
       "#maTable2 { \n",
       "  width: 100%;\n",
       "  border-collapse: collapse;\n",
       "}\n",
       "#maTable2 th, #maTable2 td {\n",
       "  padding: 3px;\n",
       "  border: 1px solid #fff;\n",
       "  text-align: center;\n",
       "}\n",
       "#maTable2 th {\n",
       "  background: #999690;\n",
       "  color: white;\n",
       "  font-weight: bold;\n",
       "}\n",
       "</style>\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from IPython.core.display import HTML\n",
    "HTML(\"\"\"\n",
    "<style>\n",
    "#maTable2 { \n",
    "  width: 100%;\n",
    "  border-collapse: collapse;\n",
    "}\n",
    "#maTable2 th, #maTable2 td {\n",
    "  padding: 3px;\n",
    "  border: 1px solid #fff;\n",
    "  text-align: center;\n",
    "}\n",
    "#maTable2 th {\n",
    "  background: #999690;\n",
    "  color: white;\n",
    "  font-weight: bold;\n",
    "}\n",
    "</style>\n",
    "\"\"\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Les complexités algorithmiques que nous allons calculer vont dorénavant être exprimées comme des grand $\\mathcal{O}$ ou grand $\\Theta$ de fonctions de références. Cela va nous permettre de les classer.\n",
    "\n",
    "Des algorithmes appartenant à une même classe seront alors considérés comme de complexité équivalente. Cela signifiera que l'on considèrera qu'ils ont la même efficacité.\n",
    "\n",
    "Le tableau suivant récapitule les complexités de référence :"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<link rel=Stylesheet type=\"text/css\" href=style.css>\n",
    "<table id=\"maTable2\">\n",
    "  <thead>\n",
    "    <tr>\n",
    "      <th>$\\mathcal{O}$</th>\n",
    "      <th>Type de complexité</th>\n",
    "    </tr>\n",
    "  </thead>\n",
    "  <tbody>\n",
    "    <tr>\n",
    "      <th>$\\mathcal{O}(1)$</th>\n",
    "      <td>constant</td>\n",
    "    </tr>\n",
    "    <tr>\n",
    "      <th>$\\mathcal{O}(\\log{}n)$</th>\n",
    "      <td>logarithmique</td>\n",
    "    </tr>\n",
    "    <tr>\n",
    "      <th>$\\mathcal{O}(n)$</th>\n",
    "      <td>linéaire</td>\n",
    "    </tr>\n",
    "    <tr>\n",
    "      <th>$\\mathcal{O}(n\\log{}n)$</th>\n",
    "      <td>quasi-linéaire</td>\n",
    "    </tr>\n",
    "    <tr>\n",
    "      <th>$\\mathcal{O}$($n^2$)</th>\n",
    "      <td>quadratique</td>\n",
    "    </tr>\n",
    "    <tr>\n",
    "      <th>$\\mathcal{O}$($n^3$)</th>\n",
    "      <td>cubique</td>\n",
    "    </tr>\n",
    "    <tr>\n",
    "      <th>$\\mathcal{O}$($2^n$)</th>\n",
    "      <td>exponentiel</td>\n",
    "    </tr>\n",
    "    <tr>\n",
    "      <th>$\\mathcal{O}$($n$!)</th>\n",
    "      <td>factoriel</td>\n",
    "    </tr>\n",
    "  </tbody>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <font color=#3876C2> Chapitre 2 - Premiers calculs de complexité : algorithmes itératifs</font> <a name=\"M2\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Avant de commencer, voici notre hypothèse de base : toutes les opérations élémentaires sont à égalité de coût. Cela permet donc d'affirmer que le temps d'exécution est proportionnel au nombre de ces opérations élémentaires.  On dit qu'on adopte le **modèle à coût fixe**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <font color=#FEB229> 1. Algorithmes sans structures de contrôle</font> <a name=\"M21\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "une structure de contrôle est une structure itérative ou une structure conditionnelle. Si un algorithme n'en comporte pas, pour évaluer sa complexité il suffit juste de dénombrer le nombre d’opérations T(n) successives qu'il possède."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction suivante convertit un nombre de secondes en heures, minutes, secondes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def conversion(n):\n",
    "    h = n // 3600\n",
    "    m = (n - 3600*h) // 60\n",
    "    s = n % 60\n",
    "    return h,m,s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(13, 53, 20)"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "conversion(50000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cet algorithme ne comporte pas de structures de contrôle.\n",
    "\n",
    "On peut dénombrer cinq opérations arithmétiques et trois affectations. On a donc \n",
    "T(n) = 8. La complexité (ou coût) en temps de cet algorithme C(n) = $\\mathcal{O}(1)$ est donc constante (car 8/1 est borné par 7 et 9 par exemple)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <font color=#FEB229> 2. Le cas des structures conditionnelles</font> <a name=\"M22\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "En présence d'une structure conditionnelle, il faut commencer par dénombrer le nombre de conditions du test.\n",
    "\n",
    "On décompte ensuite le nombre d’opérations élémentaires de chacune des alternatives, et l'on prend le maximum de ce décompte afin d'obtenir la complexité dans le pire des cas."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction suivante calcule $(-1)^{n}$ sans effectuer de produit mais en utilisant un test avec une alternative :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def puissanceMoinsUn(n):\n",
    "    if n%2==0:\n",
    "        res = 1\n",
    "    else:\n",
    "        res = -1\n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-1"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "puissanceMoinsUn(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le test de la conditionnelle comporte une opération arithmétique et une comparaison.\n",
    "\n",
    "Chaque alternative possède une affectation, ainsi le maximum des coûts des différentes alternatives est de 3.\n",
    "\n",
    "On a donc T(n) = 3; La complexité (ou coût) en temps de cet algorithme C(n) =  $\\mathcal{O}(1)$  est donc constante (car $\\frac{3}{1}$ est borné par 2 et 4 par exemple)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <font color=#FEB229> 3. Le cas des structures itératives </font> <a name=\"M23\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Il y a deux possibilités lors du traitement d'une structure itérative.\n",
    "\n",
    "Si chaque itération comporte le même nombre d'opérations élémentaires, pour évaluer la complexité il suffit de multiplier le nombre d'itérations par le nombre d'opérations de chacune d'elles.\n",
    "\n",
    "Si chaque itération ne possède pas le même nombre d'opérations, il faudra alors distinguer ces itérations, c'est-à-dire évaluer la complexité de chacune d'elle puis en faire la somme.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cette fonction utilise une structure for pour calculer la somme des n premiers entiers :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def sommeEntiers(n):\n",
    "    somme = 0\n",
    "    for i in range(n+1):\n",
    "        somme += i\n",
    "    return somme"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "36"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sommeEntiers(8)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ici chaque itération a le même nombre d’opérations, à savoir cinq : deux affections (i et somme), deux additions (i et somme) et une comparaison.\n",
    "\n",
    "On a d'autre part une affectation, lors de l'initialisation de la variable somme.\n",
    "\n",
    "Ainsi \n",
    "T(n) = 5n+1. La complexité (ou coût) en temps de cet algorithme C(n) =  $\\mathcal{O}(n)$  est donc linéaire (car $\\frac{5n+1}{n}$ est borné par 5 et 6 par exemple).\n",
    "\n",
    "Une autre méthode pour calculer cette somme est d'utiliser une formule explicite."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def sommeEntiersBis(n):\n",
    "    return n*(n+1)//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "36"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sommeEntiersBis(8)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cet algorithme ne comporte pas de structures de contrôle, il est juste constitué de trois opérations arithmétiques.\n",
    "\n",
    "On a donc T(n)=3 . La complexité (ou coût) en temps de cet algorithme C(n) =  $\\mathcal{O}(1)$  est donc constante (car $\\frac{3}{1}$ est borné par 2 et 4 par exemple)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <font color=#FEB229> 4. Autres exemples</font> <a name=\"M24\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Recherche séquentielle d'un élément dans une liste"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction suivante recherche l'élément x dans la liste l. Si x appartient à l elle retourne l'indice de la première occurence de x dans l, sinon elle retourne -1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def recherche(l,x):\n",
    "    for i in range(len(l)):\n",
    "        if l[i]==x:\n",
    "            return i\n",
    "    return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "recherche([2,5,7,9],7)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ici la complexité sera fonction de la longueur de la liste, que nous noterons n.\n",
    "\n",
    "Dans le pire des cas l'élément recherché n'appartient pas à la liste, et il a fallu la parcourir en entier pour arriver à cette conclusion, c'est-à-dire effectuer n itérations.\n",
    "\n",
    "De plus, chaque itération comporte le même nombre d'opérations élémentaires, à savoir une affectation, une addition et deux comparaisons.\n",
    "\n",
    "On a donc T(n) = 4n. La complexité (ou coût) en temps de cet algorithme C(n) =  $\\mathcal{O}(n)$  est donc linéaire (car $\\frac{4n}{n}$ est borné par 3 et 5 par exemple)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <font color=#FEB229> (Exercice 1) Au programme de première NSI : tri par sélection</font> <a name=\"M25\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<figure>\n",
    "<img src=\"extrait2.png\">\n",
    "<center><figcation>Extrait du programme NSI première</figcation></center>\n",
    "</figure>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Tri par sélection"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le tri par sélection est un algorithme itératif réalisant le tri par ordre croissant d'une liste.\n",
    "\n",
    "Il consiste dans un premier temps à mettre à la première place le plus petit élément de la liste, puis à la seconde place le deuxième plus petit élément, etc.\n",
    "\n",
    "Sa description est la suivante :\n",
    "\n",
    "*  Rechercher dans la liste la plus petite valeur et la permuter avec le premier élément de la liste.\n",
    "\n",
    "*  Rechercher ensuite la plus petite valeur à partir de la deuxième case et la permuter avec le second élément de la liste.\n",
    "\n",
    "*  Et ainsi de suite jusqu’à avoir parcouru toute la liste.\n",
    "\n",
    "En voici son implémentation en Python :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def triSelection(l):\n",
    "    for i in range(len(l)-1):\n",
    "        indMini=i\n",
    "        for j in range(i+1,len(l)):\n",
    "            if l[j]<l[indMini]:\n",
    "                indMini=j\n",
    "        l[i],l[indMini]=l[indMini],l[i]\n",
    "    return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 5, 7, 7, 9]"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "triSelection([2,1,5,7,9,7])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Déterminer la complexité de la fonction triSelection"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ici aussi la complexité sera fonction de la longueur n de la liste.\n",
    "\n",
    "Le pire des cas correspond à une liste triée par ordre décroissant.\n",
    "\n",
    "Chaque itération de la boucle principale, la plus externe, ne possède pas le même nombre d'opérations. Il y a toujours les mêmes (les opérations concernant la variable i, l'initialisation de indMini et l'échange des valeurs), plus les opérations dues à la boucle la plus interne, qui elles sont en nombre variable.\n",
    "\n",
    "Le nombre d'itérations de la boucle interne varie d'une itération à l'autre de la boucle externe :\n",
    "\n",
    "à la première itération de la boucle externe la variable i vaut 0 et la boucle interne effectue donc n - 1 itérations.\n",
    "\n",
    "à la seconde itération de la boucle externe la variable i vaut 1 et la boucle interne effectue donc n - 2 itérations.\n",
    "\n",
    "etc.\n",
    "\n",
    "Pour déterminer la complexité de cet algorithme il suffit de calculer la somme du nombre d'opérations de chaque itération de la boucle externe (les autres opérations ne la modifiant pas. A savoir\n",
    "\n",
    "( n − 1 ) + ( n − 2 ) + . . . +  1 =  $\\frac{(n \\: - \\:1)(1 \\:+ \\:n\\: - \\:1)}{2}$\n",
    "                                   =  $\\frac{(n \\: - \\:1)n}{2}$\n",
    "\n",
    "Conclusion, la complexité dans le pire des cas du tri par sélection est C(n) =  $\\mathcal{O}(n^2)$ est donc quadratique (car $\\frac{\\frac{(n \\: - \\:1)n}{2}}{n^2}$ est borné par 0 et 1 par exemple)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <font color=#FEB229> (Exercice 2) Au programme de première NSI : tri par insertion</font> <a name=\"M26\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Tri par insertion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "L’idée est de trier progressivement le tableau : supposant que t [0 : k] est déjà trié, j’insère t [k] à sa place parmi les valeurs de t [0 : k] (en décalant les plus grandes valeurs d’un cran vers la droite si nécessaire) de sorte que t [0 : k + 1] se retrouve trié.\n",
    "Le principe de modularité pourrait nous conduire à écrire une fonction qui détermine la place de t [k], puis une deuxième fonction qui se charge de l’insertion. On obtient un code plus compact en décalant les valeurs au fur et à mesure de la recherche de la place de t [k] (sans oublier de mémoriser la valeur de t [k], qui risque d’être écrasée très vite !).\n",
    "Plus précisément, pour k allant de 1 à n − 1 :"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "-\tje stocke la valeur de t [k] dans une variable temp et j’initialise j à la valeur k\n",
    "-\ttant que j > 0 et temp < t [j − 1] (j’ai une valeur supérieure à temp à gauche de t [j]), je décale t [j − 1] d’un cran vers la droite et je décrémente j\n",
    "-\tà la sortie de la boucle j’installe temp à sa place."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ici vous allez effectuer un exercice autoévalué qui va consister à écrire la fonction qui retourne une liste triée par insertion trois cellules plus bas"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# chargement de l'exercice\n",
    "from corrections.exo_tri_insertion import exo_tri_insertion"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<table style='font-family:monospace;font-size:small;'><tr style='font-family:monospace;font-size:medium;'><th style='text-align: center;'>Appel</th><th style='text-align: center;'>Résultat Attendu</th></tr><tr><td><pre>tri_insertion(\n",
       "  [1, 10, 3, 5])\n",
       "</pre></td><td><pre>\n",
       "[1, 3, 5, 10]</pre></td></tr></table>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# exemple de sortie\n",
    "exo_tri_insertion.example()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def tri_insertion(list):\n",
    "    '''la liste list est triée à l'aide de la méthode du tri par insertion'''\n",
    "    for k in range(1,len(list)):\n",
    "        temp=list[k]\n",
    "        j=k\n",
    "        while j>0 and temp<list[j-1]:\n",
    "            list[j]=list[j-1]\n",
    "            j-=1\n",
    "        list[j]=temp\n",
    "    return list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<table style='font-family:monospace;font-size:small;'><tr style='font-family:monospace;font-size:medium;'><th style='text-align: center;'>Appel</th><th style='text-align: center;'>Attendu</th><th style='text-align: center;'>Obtenu</th><th style='text-align: center;'></th></tr><tr style='background-color:#d6e9ce;'><td><pre>tri_insertion(\n",
       "  [1, 10, 3, 5])\n",
       "</pre></td><td><pre>\n",
       "[1, 3, 5, 10]</pre></td><td><pre>\n",
       "[1, 3, 5, 10]</pre></td><td>OK</td></tr><tr style='background-color:#d6e9ce;'><td><pre>tri_insertion(\n",
       "  [10, 2, 8, 1, 0])\n",
       "</pre></td><td><pre>\n",
       "[0, 1, 2, 8, 10]</pre></td><td><pre>\n",
       "[0, 1, 2, 8, 10]</pre></td><td>OK</td></tr><tr style='background-color:#d6e9ce;'><td>tri_insertion([5, 1, 3])</td><td><pre>\n",
       "[1, 3, 5]</pre></td><td><pre>\n",
       "[1, 3, 5]</pre></td><td>OK</td></tr><tr style='background-color:#d6e9ce;'><td><pre>tri_insertion(\n",
       "  [ 15,\n",
       "    10,\n",
       "    14,\n",
       "    12,\n",
       "    8,\n",
       "    21])\n",
       "</pre></td><td><pre>\n",
       "[8, 10, 12, 14, 15, 21]</pre></td><td><pre>\n",
       "[8, 10, 12, 14, 15, 21]</pre></td><td>OK</td></tr></table>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# pour vérifier votre code\n",
    "exo_tri_insertion.correction(tri_insertion)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Terminaison"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "- Une boucle for termine toujours.\n",
    "- Dans la boucle while : j est un variant de boucle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Correction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La preuve nécessite 2 invariants de boucle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "- un pour la boucle for : A la fin de la lème itération\n",
    "$$ \\forall k \\: \\in \\: \\:0..l \\:, T[k − 1]\\:  \\le \\:T[k ] $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "- un pour la boucle while : A la fin de la jème itération\n",
    "$$ \\forall k \\: \\in \\: \\:l\\:-\\:j..l\\:-\\:1 \\:, temp\\:  \\lt \\:T[k ] $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Complexité"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le nombre de comparaisons pour un tableau de taille n est :"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "** Au pire** $$ \\sum_{k=1}^{n-1}k \\:=\\: \\frac{n(n\\:-\\:1)}{2} \\: = \\:\\mathcal{O}(n^2) \\: $$ si liste \"inversée\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "** Au mieux** $$ \\sum_{k=1}^{n-1}1 \\:=\\: n\\:-\\:1\\: = \\:\\mathcal{O}(n) \\: $$ si liste déjà triée"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "WutjLZrOQpAn"
   },
   "source": [
    "## <font color=#3876C2> Chapitre 3 - Cas des algorithmes récursifs</font> <a name=\"M3\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "Nous allons maintenant nous intéresser aux cas des algorithmes récursifs, qui sont rappelons-le des sous-programmes qui s'appellent eux-mêmes. Les techniques utilisées seront relativement différentes, puisque l'on devra composer avec des suites définies par récurrence plutôt qu'avec des calculs de sommes.\n",
    "\n",
    "Nous commencerons par des récursivités simples (fonction factorielle, problème des tours de Hanoï) puis nous traiterons le cas plus difficile des algorithmes de type diviser pour régner."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <font color=#FEB229> 1. Récursivités simples  </font> <a name=\"M31\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dans un algorithme itératif, le décompte du nombre d'opérations élémentaires se fait en additionnant le nombre d'opérations de chaque itération. C'est pourquoi dans le chapitre précédent nous avons souvent utilisé des calculs de sommes pour arriver à nos fins.\n",
    "\n",
    "La complexité d’un algorithme récursif traitant des données d'une certaine taille va quant à elle naturellement dépendre de la complexité du même algorithme avec des données de taille inférieure. Cette complexité va donc être une suite définie par récurrence."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " ### <font color=#FEB229> 2. Suites arithmético-géométriques  </font> <a name=\"M32\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Définition"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$ Une \\:suite \\:réelle \\:(u_n)_{n \\in \\mathbb{N}}  \\:est \\:dite \\:arithmético-géométrique \\:s'il \\:existe \\:deux \\:réels \\:a \\:et \\:b \\:tels \\:que \\: \n",
    "\\forall n \\: \\in \\mathbb{N^*},\\: u_n \\:=\\: au_{n-1} \\: + \\:b$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Propriété"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$ Soit \\:(u_n)_{n \\in \\mathbb{N}}  \\:une \\:suite \\:arithmético-géométrique \\\n",
    "\\:associée \\:aux \\:réels \\:a \\:et \\:b.$$\n",
    "$$\\:On \\:suppose \\:que \\: a, \\:b \\:et \\:u_{0} \\:sont \\:positifs.$$\n",
    "$$Si \\:a \\:= \\:1, \\:u_n \\:= \\:\\mathcal{O}(n).$$\n",
    "$$Si \\:a \\:> \\:1, \\:u_n \\:= \\:\\mathcal{O}(a^n).$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exemple 1 : factorielle"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def factorielleRecursive(n):\n",
    "    if n == 0:\n",
    "        return 1\n",
    "    else:\n",
    "        return n*factorielleRecursive(n-1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cette fonction n'est composée que d'une structure conditionelle.\n",
    "\n",
    "Si n > 0 , une opération élémentaire (une comparaison) est effectuée lors du test, et une autre (un produit) lors de l'appel récursif. On a donc dans ce cas T(n) = T(n−1) + 2.\n",
    "Si n = 0, seule la comparaison a lieu donc T(0) = 1.\n",
    "\n",
    "La complexité T est donc une suite arithmético-géométrique associée aux constantes a = 1 et b  =2.\n",
    "\n",
    "D'après les résultats précédents, on a alors T(n)=1+2n et surtout T(n) = $\\mathcal{O}(n)$. \n",
    "Cet algorithme est donc de complexité linéaire."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "A noter que l'algorithme itératif calculant cette factorielle a la même complexité."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def factorielleIterative(n):\n",
    "    resultat = 1\n",
    "    for i in range(2,n+1):\n",
    "        resultat *= i\n",
    "    return resultat"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On a une structure for qui réalise n − 1 itérations, chacune comportant le même nombre fixe d'opérations élémentaires. C'est pourquoi là aussi T(n)= $\\mathcal{O}(n)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exemple 2 : Hanoï"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1  vers  3\n",
      "1  vers  2\n",
      "3  vers  2\n",
      "1  vers  3\n",
      "2  vers  1\n",
      "2  vers  3\n",
      "1  vers  3\n"
     ]
    }
   ],
   "source": [
    "def hanoi(de,vers,via,n):\n",
    "    if n==1:\n",
    "        print(de,\" vers \",vers)\n",
    "    else:\n",
    "        hanoi(de,via,vers,n-1)\n",
    "        print(de,\" vers \",vers)\n",
    "        hanoi(via,vers,de,n-1)\n",
    "\n",
    "\n",
    "hanoi(\"1\",\"3\",\"2\",3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Venons-en maintenant au calcul de la complexité de cette procédure qui n'est composée que d'une structure conditionnelle.\n",
    "\n",
    "Si n > 1, une opération élémentaire (une comparaison) est effectuée lors du test, une autre lors de l'affichage, et on a deux appels récursifs. On a ainsi T(n) = 2T(n−1) + 2.\n",
    "\n",
    "Si n = 1, seule la comparaison a lieu donc T(1) = 1.\n",
    "\n",
    "La complexité T est donc une suite arithmético-géométrique associée aux constantes a = 2 et b = 2.\n",
    "\n",
    "D’après le résultat précédent, on a alors T(n) = $\\mathcal{O}(2^n)$. \n",
    "Cet algorithme est donc de complexité exponentielle."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <font color=#FEB229> 3. Algorithmes de type \"diviser pour régner\" : exemple du tri fusion  </font> <a name=\"M33\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le tri fusion consiste à trier récursivement les deux moitiés de la liste, puis à fusionner ces deux sous-listes triées en une seule. La condition d’arrêt à la récursivité sera l’obtention d'une liste à un seul élément, car une telle liste est évidemment déjà triée."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Voici donc les trois étapes (diviser, régner et combiner) de cet algorithme :\n",
    "\n",
    "- Diviser la liste en deux sous-listes de même taille (à un élément près) en la \"coupant\" par la moitié.\n",
    "\n",
    "- Trier récursivement chacune de ces deux sous-listes. Arrêter la récursion lorsque les listes n'ont plus qu'un seul élément.\n",
    "\n",
    "- Fusionner les deux sous-listes triées en une seule."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On considère la liste suivante de sept entiers :"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<figure>\n",
    "<img src=\"Fusion1.png\">\n",
    "</figure>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On la scinde en deux sous-listes en la coupant par la moitié :"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<figure>\n",
    "<img src=\"Fusion2.png\">\n",
    "</figure>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sous-listes que l’on scinde à leur tour :"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<figure>\n",
    "<img src=\"Fusion3.png\">\n",
    "</figure>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ces sous-listes sont triées car elles n’ont qu’un élément. On va maintenant les fusionner deux par deux en de nouvelles sous-listes triées :"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<figure>\n",
    "<img src=\"Fusion4.png\">\n",
    "</figure>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "De nouveau une étape de fusionnnement :"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<figure>\n",
    "<img src=\"Fusion5.png\">\n",
    "</figure>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Une dernière fusion :"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "<figure>\n",
    "<img src=\"Fusion6.png\">\n",
    "</figure>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On a fusionné toutes les sous-listes obtenues lors des appels récursifs, le tri est terminé :"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<figure>\n",
    "<img src=\"Fusion7.png\">\n",
    "<center><figcation>Déroulement du tri fusion sur un exemple</figcation></center>\n",
    "</figure>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Théorème**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La complexité du tri fusion est T(n) = $\\mathcal{O}(nlog_2(n))$.\n",
    "\n",
    "Il s'agit de la meilleure complexité que puisse avoir un algorithme de tri."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Démonstration**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<figure>\n",
    "<img src=\"dem.png\">\n",
    "</figure>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <font color=#FEB229> (Exercice 3) Implémentation du tri fusion  </font> <a name=\"M34\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A vous d'en déterminer son implémentation en Python :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def fusion(l,first,middle,last):\n",
    "    i,j = first,middle+1\n",
    "    pro = []\n",
    "    while (i<=middle) and (j<=last):\n",
    "        if l[i]<=l[j]:\n",
    "            pro.append(l[i])\n",
    "            i+=1\n",
    "        else:\n",
    "            pro.append(l[j])\n",
    "            j+=1\n",
    "    while i<=middle:\n",
    "        pro.append(l[i])\n",
    "        i+=1\n",
    "    while j<=last:\n",
    "        pro.append(l[j])\n",
    "        j+=1\n",
    "    for k in range(last-first+1):\n",
    "        l[first+k] = pro[k]\n",
    "\n",
    "def triFusionRec(l,first,last):\n",
    "    if first<last:\n",
    "        triFusionRec(l,first,(first+last)//2)\n",
    "        triFusionRec(l,((first+last)//2)+1,last)\n",
    "        fusion(l,first,(first+last)//2,last)\n",
    "\n",
    "def triFusion(l):\n",
    "    triFusionRec(l,0,len(l)-1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Ressources utiles pour terminaison, correction et complexité des principaux algorithmes de tri**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "http://mathieu.gourcy.free.fr/cariboost_files/coursTrisIVP.pdf\n",
    "http://michel.stainer.pagesperso-orange.fr/PSIx/Informatique/Cours/Ch2-Tris.pdf"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <font color=#3876C2> Chapitre 4 - Un problème de dichotimie</font> <a name=\"M4\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <font color=#FEB229> (Exercice 4) Question 1</font> <a name=\"M41\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "En procédant par dichotomie, écrire en Python une fonction carre_parfait(n) prenant en argument un entier\n",
    "n et retournant True si n est un carré parfait (donc s’il existe un entier k tel que $k^2$ = n) et False sinon.\n",
    "L’utilisation de la fonction racine (sqrt) est ici interdite et la méthode de dichotomie est imposée."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Correction**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def carre_parfait(n):\n",
    "    if n == 0 or n == 1:\n",
    "        return True\n",
    "    carre = False\n",
    "    a = 0\n",
    "    b = n\n",
    "    while not carre and b - a > 1:\n",
    "        c = (a+b) // 2\n",
    "        if c*c == n:\n",
    "            carre = True\n",
    "        elif c*c > n:\n",
    "            b = c\n",
    "        else:\n",
    "            a = c\n",
    "    return carre"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "print(carre_parfait(48))\n",
    "print(carre_parfait(49))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <font color=#FEB229> (Exercice 4) Question 2</font> <a name=\"M42\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Soit $ n \\: \\in \\mathbb{N^*}$. Écrire en Python une fonction pythagicien(n) retournant une liste constituée de tous les triplets\n",
    "pythagoriciens (a, b, c) avec c $\\le$ 1000, c’est-à-dire tous les triplets d’entiers strictement positifs (a, b, c) tels que\n",
    "a² + b² = c². Déterminer la complexité de l'algorithme obtenu."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Correction**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On modifie très légèrement l’algorithme suivant de sorte à ce qu’il ressorte également la valeur de la racine,\n",
    "lorsque n est un carré parfait. Il ressort (False,0) si ce n’est pas un carré parfait"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def carre_parfait_bis(n):\n",
    "    if n == 0 :\n",
    "        return True, 0\n",
    "    if n == 1 :\n",
    "        return True, 1\n",
    "    carre = False\n",
    "    a = 0\n",
    "    b = n\n",
    "    while not carre and b - a > 1:\n",
    "        c = (a+b) // 2\n",
    "        if c*c == n:\n",
    "            carre = True\n",
    "        elif c*c > n:\n",
    "            b = c\n",
    "        else:\n",
    "            a = c\n",
    "    return False, 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On peut alors trouver les triplets pythagoriciens en testant si c² −b² est un carré parfait, pour toutes les valeurs\n",
    "possibles du couple (c, b), et si oui, en ajoutant le triplet (a, b, c) à l’ensemble des solutions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def pythagoricien(n):\n",
    "    carre =[]\n",
    "    est_carre = (n*n+1)*[0]\n",
    "    for k in range(n+1):\n",
    "        l= k*k\n",
    "        carre.append(l)\n",
    "        est_carre[l] = k\n",
    "    pyth = []\n",
    "    for c in range(1,n+1):\n",
    "        for b in range(1,c):\n",
    "            d = carre[c]-carre[b]\n",
    "            if est_carre[d]!=0:\n",
    "                pyth.append((est_carre[d],b,c))\n",
    "    return pyth"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(4, 3, 5),\n",
       " (3, 4, 5),\n",
       " (8, 6, 10),\n",
       " (6, 8, 10),\n",
       " (12, 5, 13),\n",
       " (5, 12, 13),\n",
       " (12, 9, 15),\n",
       " (9, 12, 15),\n",
       " (15, 8, 17),\n",
       " (8, 15, 17),\n",
       " (16, 12, 20),\n",
       " (12, 16, 20),\n",
       " (24, 7, 25),\n",
       " (20, 15, 25),\n",
       " (15, 20, 25),\n",
       " (7, 24, 25),\n",
       " (24, 10, 26),\n",
       " (10, 24, 26),\n",
       " (21, 20, 29),\n",
       " (20, 21, 29),\n",
       " (24, 18, 30),\n",
       " (18, 24, 30),\n",
       " (30, 16, 34),\n",
       " (16, 30, 34),\n",
       " (28, 21, 35),\n",
       " (21, 28, 35),\n",
       " (35, 12, 37),\n",
       " (12, 35, 37),\n",
       " (36, 15, 39),\n",
       " (15, 36, 39),\n",
       " (32, 24, 40),\n",
       " (24, 32, 40),\n",
       " (40, 9, 41),\n",
       " (9, 40, 41),\n",
       " (36, 27, 45),\n",
       " (27, 36, 45),\n",
       " (48, 14, 50),\n",
       " (40, 30, 50),\n",
       " (30, 40, 50),\n",
       " (14, 48, 50),\n",
       " (45, 24, 51),\n",
       " (24, 45, 51),\n",
       " (48, 20, 52),\n",
       " (20, 48, 52),\n",
       " (45, 28, 53),\n",
       " (28, 45, 53),\n",
       " (44, 33, 55),\n",
       " (33, 44, 55),\n",
       " (42, 40, 58),\n",
       " (40, 42, 58),\n",
       " (48, 36, 60),\n",
       " (36, 48, 60),\n",
       " (60, 11, 61),\n",
       " (11, 60, 61),\n",
       " (63, 16, 65),\n",
       " (60, 25, 65),\n",
       " (56, 33, 65),\n",
       " (52, 39, 65),\n",
       " (39, 52, 65),\n",
       " (33, 56, 65),\n",
       " (25, 60, 65),\n",
       " (16, 63, 65),\n",
       " (60, 32, 68),\n",
       " (32, 60, 68),\n",
       " (56, 42, 70),\n",
       " (42, 56, 70),\n",
       " (55, 48, 73),\n",
       " (48, 55, 73),\n",
       " (70, 24, 74),\n",
       " (24, 70, 74),\n",
       " (72, 21, 75),\n",
       " (60, 45, 75),\n",
       " (45, 60, 75),\n",
       " (21, 72, 75),\n",
       " (72, 30, 78),\n",
       " (30, 72, 78),\n",
       " (64, 48, 80),\n",
       " (48, 64, 80),\n",
       " (80, 18, 82),\n",
       " (18, 80, 82),\n",
       " (84, 13, 85),\n",
       " (77, 36, 85),\n",
       " (75, 40, 85),\n",
       " (68, 51, 85),\n",
       " (51, 68, 85),\n",
       " (40, 75, 85),\n",
       " (36, 77, 85),\n",
       " (13, 84, 85),\n",
       " (63, 60, 87),\n",
       " (60, 63, 87),\n",
       " (80, 39, 89),\n",
       " (39, 80, 89),\n",
       " (72, 54, 90),\n",
       " (54, 72, 90),\n",
       " (84, 35, 91),\n",
       " (35, 84, 91),\n",
       " (76, 57, 95),\n",
       " (57, 76, 95),\n",
       " (72, 65, 97),\n",
       " (65, 72, 97),\n",
       " (96, 28, 100),\n",
       " (80, 60, 100),\n",
       " (60, 80, 100),\n",
       " (28, 96, 100),\n",
       " (99, 20, 101),\n",
       " (20, 99, 101),\n",
       " (90, 48, 102),\n",
       " (48, 90, 102),\n",
       " (96, 40, 104),\n",
       " (40, 96, 104),\n",
       " (84, 63, 105),\n",
       " (63, 84, 105),\n",
       " (90, 56, 106),\n",
       " (56, 90, 106),\n",
       " (91, 60, 109),\n",
       " (60, 91, 109),\n",
       " (88, 66, 110),\n",
       " (66, 88, 110),\n",
       " (105, 36, 111),\n",
       " (36, 105, 111),\n",
       " (112, 15, 113),\n",
       " (15, 112, 113),\n",
       " (92, 69, 115),\n",
       " (69, 92, 115),\n",
       " (84, 80, 116),\n",
       " (80, 84, 116),\n",
       " (108, 45, 117),\n",
       " (45, 108, 117),\n",
       " (105, 56, 119),\n",
       " (56, 105, 119),\n",
       " (96, 72, 120),\n",
       " (72, 96, 120),\n",
       " (120, 22, 122),\n",
       " (22, 120, 122),\n",
       " (120, 27, 123),\n",
       " (27, 120, 123),\n",
       " (120, 35, 125),\n",
       " (117, 44, 125),\n",
       " (100, 75, 125),\n",
       " (75, 100, 125),\n",
       " (44, 117, 125),\n",
       " (35, 120, 125),\n",
       " (126, 32, 130),\n",
       " (120, 50, 130),\n",
       " (112, 66, 130),\n",
       " (104, 78, 130),\n",
       " (78, 104, 130),\n",
       " (66, 112, 130),\n",
       " (50, 120, 130),\n",
       " (32, 126, 130),\n",
       " (108, 81, 135),\n",
       " (81, 108, 135),\n",
       " (120, 64, 136),\n",
       " (64, 120, 136),\n",
       " (105, 88, 137),\n",
       " (88, 105, 137),\n",
       " (112, 84, 140),\n",
       " (84, 112, 140),\n",
       " (132, 55, 143),\n",
       " (55, 132, 143),\n",
       " (144, 17, 145),\n",
       " (143, 24, 145),\n",
       " (116, 87, 145),\n",
       " (105, 100, 145),\n",
       " (100, 105, 145),\n",
       " (87, 116, 145),\n",
       " (24, 143, 145),\n",
       " (17, 144, 145),\n",
       " (110, 96, 146),\n",
       " (96, 110, 146),\n",
       " (140, 48, 148),\n",
       " (48, 140, 148),\n",
       " (140, 51, 149),\n",
       " (51, 140, 149),\n",
       " (144, 42, 150),\n",
       " (120, 90, 150),\n",
       " (90, 120, 150),\n",
       " (42, 144, 150),\n",
       " (135, 72, 153),\n",
       " (72, 135, 153),\n",
       " (124, 93, 155),\n",
       " (93, 124, 155),\n",
       " (144, 60, 156),\n",
       " (60, 144, 156),\n",
       " (132, 85, 157),\n",
       " (85, 132, 157),\n",
       " (135, 84, 159),\n",
       " (84, 135, 159),\n",
       " (128, 96, 160),\n",
       " (96, 128, 160),\n",
       " (160, 36, 164),\n",
       " (36, 160, 164),\n",
       " (132, 99, 165),\n",
       " (99, 132, 165),\n",
       " (156, 65, 169),\n",
       " (120, 119, 169),\n",
       " (119, 120, 169),\n",
       " (65, 156, 169),\n",
       " (168, 26, 170),\n",
       " (154, 72, 170),\n",
       " (150, 80, 170),\n",
       " (136, 102, 170),\n",
       " (102, 136, 170),\n",
       " (80, 150, 170),\n",
       " (72, 154, 170),\n",
       " (26, 168, 170),\n",
       " (165, 52, 173),\n",
       " (52, 165, 173),\n",
       " (126, 120, 174),\n",
       " (120, 126, 174),\n",
       " (168, 49, 175),\n",
       " (140, 105, 175),\n",
       " (105, 140, 175),\n",
       " (49, 168, 175),\n",
       " (160, 78, 178),\n",
       " (78, 160, 178),\n",
       " (144, 108, 180),\n",
       " (108, 144, 180),\n",
       " (180, 19, 181),\n",
       " (19, 180, 181),\n",
       " (168, 70, 182),\n",
       " (70, 168, 182),\n",
       " (180, 33, 183),\n",
       " (33, 180, 183),\n",
       " (176, 57, 185),\n",
       " (175, 60, 185),\n",
       " (153, 104, 185),\n",
       " (148, 111, 185),\n",
       " (111, 148, 185),\n",
       " (104, 153, 185),\n",
       " (60, 175, 185),\n",
       " (57, 176, 185),\n",
       " (165, 88, 187),\n",
       " (88, 165, 187),\n",
       " (152, 114, 190),\n",
       " (114, 152, 190),\n",
       " (168, 95, 193),\n",
       " (95, 168, 193),\n",
       " (144, 130, 194),\n",
       " (130, 144, 194),\n",
       " (189, 48, 195),\n",
       " (180, 75, 195),\n",
       " (168, 99, 195),\n",
       " (156, 117, 195),\n",
       " (117, 156, 195),\n",
       " (99, 168, 195),\n",
       " (75, 180, 195),\n",
       " (48, 189, 195),\n",
       " (195, 28, 197),\n",
       " (28, 195, 197),\n",
       " (192, 56, 200),\n",
       " (160, 120, 200),\n",
       " (120, 160, 200),\n",
       " (56, 192, 200),\n",
       " (198, 40, 202),\n",
       " (40, 198, 202),\n",
       " (147, 140, 203),\n",
       " (140, 147, 203),\n",
       " (180, 96, 204),\n",
       " (96, 180, 204),\n",
       " (200, 45, 205),\n",
       " (187, 84, 205),\n",
       " (164, 123, 205),\n",
       " (156, 133, 205),\n",
       " (133, 156, 205),\n",
       " (123, 164, 205),\n",
       " (84, 187, 205),\n",
       " (45, 200, 205),\n",
       " (192, 80, 208),\n",
       " (80, 192, 208),\n",
       " (168, 126, 210),\n",
       " (126, 168, 210),\n",
       " (180, 112, 212),\n",
       " (112, 180, 212),\n",
       " (172, 129, 215),\n",
       " (129, 172, 215),\n",
       " (182, 120, 218),\n",
       " (120, 182, 218),\n",
       " (165, 144, 219),\n",
       " (144, 165, 219),\n",
       " (176, 132, 220),\n",
       " (132, 176, 220),\n",
       " (220, 21, 221),\n",
       " (204, 85, 221),\n",
       " (195, 104, 221),\n",
       " (171, 140, 221),\n",
       " (140, 171, 221),\n",
       " (104, 195, 221),\n",
       " (85, 204, 221),\n",
       " (21, 220, 221),\n",
       " (210, 72, 222),\n",
       " (72, 210, 222),\n",
       " (216, 63, 225),\n",
       " (180, 135, 225),\n",
       " (135, 180, 225),\n",
       " (63, 216, 225),\n",
       " (224, 30, 226),\n",
       " (30, 224, 226),\n",
       " (221, 60, 229),\n",
       " (60, 221, 229),\n",
       " (184, 138, 230),\n",
       " (138, 184, 230),\n",
       " (168, 160, 232),\n",
       " (160, 168, 232),\n",
       " (208, 105, 233),\n",
       " (105, 208, 233),\n",
       " (216, 90, 234),\n",
       " (90, 216, 234),\n",
       " (188, 141, 235),\n",
       " (141, 188, 235),\n",
       " (210, 112, 238),\n",
       " (112, 210, 238),\n",
       " (192, 144, 240),\n",
       " (144, 192, 240),\n",
       " (209, 120, 241),\n",
       " (120, 209, 241),\n",
       " (240, 44, 244),\n",
       " (44, 240, 244),\n",
       " (196, 147, 245),\n",
       " (147, 196, 245),\n",
       " (240, 54, 246),\n",
       " (54, 240, 246),\n",
       " (228, 95, 247),\n",
       " (95, 228, 247),\n",
       " (240, 70, 250),\n",
       " (234, 88, 250),\n",
       " (200, 150, 250),\n",
       " (150, 200, 250),\n",
       " (88, 234, 250),\n",
       " (70, 240, 250),\n",
       " (252, 39, 255),\n",
       " (231, 108, 255),\n",
       " (225, 120, 255),\n",
       " (204, 153, 255),\n",
       " (153, 204, 255),\n",
       " (120, 225, 255),\n",
       " (108, 231, 255),\n",
       " (39, 252, 255),\n",
       " (255, 32, 257),\n",
       " (32, 255, 257),\n",
       " (245, 84, 259),\n",
       " (84, 245, 259),\n",
       " (252, 64, 260),\n",
       " (240, 100, 260),\n",
       " (224, 132, 260),\n",
       " (208, 156, 260),\n",
       " (156, 208, 260),\n",
       " (132, 224, 260),\n",
       " (100, 240, 260),\n",
       " (64, 252, 260),\n",
       " (189, 180, 261),\n",
       " (180, 189, 261),\n",
       " (264, 23, 265),\n",
       " (247, 96, 265),\n",
       " (225, 140, 265),\n",
       " (212, 159, 265),\n",
       " (159, 212, 265),\n",
       " (140, 225, 265),\n",
       " (96, 247, 265),\n",
       " (23, 264, 265),\n",
       " (240, 117, 267),\n",
       " (117, 240, 267),\n",
       " (260, 69, 269),\n",
       " (69, 260, 269),\n",
       " (216, 162, 270),\n",
       " (162, 216, 270),\n",
       " (240, 128, 272),\n",
       " (128, 240, 272),\n",
       " (252, 105, 273),\n",
       " (105, 252, 273),\n",
       " (210, 176, 274),\n",
       " (176, 210, 274),\n",
       " (264, 77, 275),\n",
       " (220, 165, 275),\n",
       " (165, 220, 275),\n",
       " (77, 264, 275),\n",
       " (252, 115, 277),\n",
       " (115, 252, 277),\n",
       " (224, 168, 280),\n",
       " (168, 224, 280),\n",
       " (231, 160, 281),\n",
       " (160, 231, 281),\n",
       " (228, 171, 285),\n",
       " (171, 228, 285),\n",
       " (264, 110, 286),\n",
       " (110, 264, 286),\n",
       " (280, 63, 287),\n",
       " (63, 280, 287),\n",
       " (255, 136, 289),\n",
       " (240, 161, 289),\n",
       " (161, 240, 289),\n",
       " (136, 255, 289),\n",
       " (288, 34, 290),\n",
       " (286, 48, 290),\n",
       " (232, 174, 290),\n",
       " (210, 200, 290),\n",
       " (200, 210, 290),\n",
       " (174, 232, 290),\n",
       " (48, 286, 290),\n",
       " (34, 288, 290),\n",
       " (216, 195, 291),\n",
       " (195, 216, 291),\n",
       " (220, 192, 292),\n",
       " (192, 220, 292),\n",
       " (285, 68, 293),\n",
       " (68, 285, 293),\n",
       " (236, 177, 295),\n",
       " (177, 236, 295),\n",
       " (280, 96, 296),\n",
       " (96, 280, 296),\n",
       " (280, 102, 298),\n",
       " (102, 280, 298),\n",
       " (276, 115, 299),\n",
       " (115, 276, 299),\n",
       " (288, 84, 300),\n",
       " (240, 180, 300),\n",
       " (180, 240, 300),\n",
       " (84, 288, 300),\n",
       " (297, 60, 303),\n",
       " (60, 297, 303),\n",
       " (300, 55, 305),\n",
       " (273, 136, 305),\n",
       " (244, 183, 305),\n",
       " (224, 207, 305),\n",
       " (207, 224, 305),\n",
       " (183, 244, 305),\n",
       " (136, 273, 305),\n",
       " (55, 300, 305),\n",
       " (270, 144, 306),\n",
       " (144, 270, 306),\n",
       " (248, 186, 310),\n",
       " (186, 248, 310),\n",
       " (288, 120, 312),\n",
       " (120, 288, 312),\n",
       " (312, 25, 313),\n",
       " (25, 312, 313),\n",
       " (264, 170, 314),\n",
       " (170, 264, 314),\n",
       " (252, 189, 315),\n",
       " (189, 252, 315),\n",
       " (308, 75, 317),\n",
       " (75, 308, 317),\n",
       " (270, 168, 318),\n",
       " (168, 270, 318),\n",
       " (231, 220, 319),\n",
       " (220, 231, 319),\n",
       " (256, 192, 320),\n",
       " (192, 256, 320),\n",
       " (285, 152, 323),\n",
       " (152, 285, 323),\n",
       " (323, 36, 325),\n",
       " (315, 80, 325),\n",
       " (312, 91, 325),\n",
       " (300, 125, 325),\n",
       " (280, 165, 325),\n",
       " (260, 195, 325),\n",
       " (253, 204, 325),\n",
       " (204, 253, 325),\n",
       " (195, 260, 325),\n",
       " (165, 280, 325),\n",
       " (125, 300, 325),\n",
       " (91, 312, 325),\n",
       " (80, 315, 325),\n",
       " (36, 323, 325),\n",
       " (273, 180, 327),\n",
       " (180, 273, 327),\n",
       " (320, 72, 328),\n",
       " (72, 320, 328),\n",
       " (264, 198, 330),\n",
       " (198, 264, 330),\n",
       " (315, 108, 333),\n",
       " (108, 315, 333),\n",
       " (268, 201, 335),\n",
       " (201, 268, 335),\n",
       " (288, 175, 337),\n",
       " (175, 288, 337),\n",
       " (312, 130, 338),\n",
       " (240, 238, 338),\n",
       " (238, 240, 338),\n",
       " (130, 312, 338),\n",
       " (336, 45, 339),\n",
       " (45, 336, 339),\n",
       " (336, 52, 340),\n",
       " (308, 144, 340),\n",
       " (300, 160, 340),\n",
       " (272, 204, 340),\n",
       " (204, 272, 340),\n",
       " (160, 300, 340),\n",
       " (144, 308, 340),\n",
       " (52, 336, 340),\n",
       " (276, 207, 345),\n",
       " (207, 276, 345),\n",
       " (330, 104, 346),\n",
       " (104, 330, 346),\n",
       " (252, 240, 348),\n",
       " (240, 252, 348),\n",
       " (299, 180, 349),\n",
       " (180, 299, 349),\n",
       " (336, 98, 350),\n",
       " (280, 210, 350),\n",
       " (210, 280, 350),\n",
       " (98, 336, 350),\n",
       " (324, 135, 351),\n",
       " (135, 324, 351),\n",
       " (272, 225, 353),\n",
       " (225, 272, 353),\n",
       " (284, 213, 355),\n",
       " (213, 284, 355),\n",
       " (320, 156, 356),\n",
       " (156, 320, 356),\n",
       " (315, 168, 357),\n",
       " (168, 315, 357),\n",
       " (288, 216, 360),\n",
       " (216, 288, 360),\n",
       " (360, 38, 362),\n",
       " (38, 360, 362),\n",
       " (336, 140, 364),\n",
       " (140, 336, 364),\n",
       " (364, 27, 365),\n",
       " (357, 76, 365),\n",
       " (292, 219, 365),\n",
       " (275, 240, 365),\n",
       " (240, 275, 365),\n",
       " (219, 292, 365),\n",
       " (76, 357, 365),\n",
       " (27, 364, 365),\n",
       " (360, 66, 366),\n",
       " (66, 360, 366),\n",
       " (360, 81, 369),\n",
       " (81, 360, 369),\n",
       " (352, 114, 370),\n",
       " (350, 120, 370),\n",
       " (306, 208, 370),\n",
       " (296, 222, 370),\n",
       " (222, 296, 370),\n",
       " (208, 306, 370),\n",
       " (120, 350, 370),\n",
       " (114, 352, 370),\n",
       " (315, 196, 371),\n",
       " (196, 315, 371),\n",
       " (275, 252, 373),\n",
       " (252, 275, 373),\n",
       " (330, 176, 374),\n",
       " (176, 330, 374),\n",
       " (360, 105, 375),\n",
       " (351, 132, 375),\n",
       " (300, 225, 375),\n",
       " (225, 300, 375),\n",
       " (132, 351, 375),\n",
       " (105, 360, 375),\n",
       " (352, 135, 377),\n",
       " (348, 145, 377),\n",
       " (345, 152, 377),\n",
       " (273, 260, 377),\n",
       " (260, 273, 377),\n",
       " (152, 345, 377),\n",
       " (145, 348, 377),\n",
       " (135, 352, 377),\n",
       " (304, 228, 380),\n",
       " (228, 304, 380),\n",
       " (308, 231, 385),\n",
       " (231, 308, 385),\n",
       " (336, 190, 386),\n",
       " (190, 336, 386),\n",
       " (288, 260, 388),\n",
       " (260, 288, 388),\n",
       " (340, 189, 389),\n",
       " (189, 340, 389),\n",
       " (378, 96, 390),\n",
       " (360, 150, 390),\n",
       " (336, 198, 390),\n",
       " (312, 234, 390),\n",
       " (234, 312, 390),\n",
       " (198, 336, 390),\n",
       " (150, 360, 390),\n",
       " (96, 378, 390),\n",
       " (345, 184, 391),\n",
       " (184, 345, 391),\n",
       " (390, 56, 394),\n",
       " (56, 390, 394),\n",
       " (316, 237, 395),\n",
       " (237, 316, 395),\n",
       " (325, 228, 397),\n",
       " (228, 325, 397),\n",
       " (384, 112, 400),\n",
       " (320, 240, 400),\n",
       " (240, 320, 400),\n",
       " (112, 384, 400),\n",
       " (399, 40, 401),\n",
       " (40, 399, 401),\n",
       " (372, 155, 403),\n",
       " (155, 372, 403),\n",
       " (396, 80, 404),\n",
       " (80, 396, 404),\n",
       " (324, 243, 405),\n",
       " (243, 324, 405),\n",
       " (294, 280, 406),\n",
       " (280, 294, 406),\n",
       " (385, 132, 407),\n",
       " (132, 385, 407),\n",
       " (360, 192, 408),\n",
       " (192, 360, 408),\n",
       " (391, 120, 409),\n",
       " (120, 391, 409),\n",
       " (400, 90, 410),\n",
       " (374, 168, 410),\n",
       " (328, 246, 410),\n",
       " (312, 266, 410),\n",
       " (266, 312, 410),\n",
       " (246, 328, 410),\n",
       " (168, 374, 410),\n",
       " (90, 400, 410),\n",
       " (315, 264, 411),\n",
       " (264, 315, 411),\n",
       " (332, 249, 415),\n",
       " (249, 332, 415),\n",
       " (384, 160, 416),\n",
       " (160, 384, 416),\n",
       " (336, 252, 420),\n",
       " (252, 336, 420),\n",
       " (420, 29, 421),\n",
       " (29, 420, 421),\n",
       " (360, 224, 424),\n",
       " (224, 360, 424),\n",
       " (420, 65, 425),\n",
       " (416, 87, 425),\n",
       " (408, 119, 425),\n",
       " (385, 180, 425),\n",
       " (375, 200, 425),\n",
       " (340, 255, 425),\n",
       " (304, 297, 425),\n",
       " (297, 304, 425),\n",
       " (255, 340, 425),\n",
       " (200, 375, 425),\n",
       " (180, 385, 425),\n",
       " (119, 408, 425),\n",
       " (87, 416, 425),\n",
       " (65, 420, 425),\n",
       " (420, 77, 427),\n",
       " (77, 420, 427),\n",
       " (396, 165, 429),\n",
       " (165, 396, 429),\n",
       " (344, 258, 430),\n",
       " (258, 344, 430),\n",
       " (408, 145, 433),\n",
       " (145, 408, 433),\n",
       " (432, 51, 435),\n",
       " (429, 72, 435),\n",
       " (348, 261, 435),\n",
       " (315, 300, 435),\n",
       " (300, 315, 435),\n",
       " (261, 348, 435),\n",
       " (72, 429, 435),\n",
       " (51, 432, 435),\n",
       " (364, 240, 436),\n",
       " (240, 364, 436),\n",
       " (330, 288, 438),\n",
       " (288, 330, 438),\n",
       " (352, 264, 440),\n",
       " (264, 352, 440),\n",
       " (440, 42, 442),\n",
       " (408, 170, 442),\n",
       " (390, 208, 442),\n",
       " (342, 280, 442),\n",
       " (280, 342, 442),\n",
       " (208, 390, 442),\n",
       " (170, 408, 442),\n",
       " (42, 440, 442),\n",
       " (420, 144, 444),\n",
       " (144, 420, 444),\n",
       " (437, 84, 445),\n",
       " (400, 195, 445),\n",
       " (396, 203, 445),\n",
       " (356, 267, 445),\n",
       " (267, 356, 445),\n",
       " (203, 396, 445),\n",
       " (195, 400, 445),\n",
       " (84, 437, 445),\n",
       " (420, 153, 447),\n",
       " (153, 420, 447),\n",
       " (351, 280, 449),\n",
       " (280, 351, 449),\n",
       " (432, 126, 450),\n",
       " (360, 270, 450),\n",
       " (270, 360, 450),\n",
       " (126, 432, 450),\n",
       " (440, 99, 451),\n",
       " (99, 440, 451),\n",
       " (448, 60, 452),\n",
       " (60, 448, 452),\n",
       " (441, 112, 455),\n",
       " (420, 175, 455),\n",
       " (392, 231, 455),\n",
       " (364, 273, 455),\n",
       " (273, 364, 455),\n",
       " (231, 392, 455),\n",
       " (175, 420, 455),\n",
       " (112, 441, 455),\n",
       " (425, 168, 457),\n",
       " (168, 425, 457),\n",
       " (442, 120, 458),\n",
       " (120, 442, 458),\n",
       " (405, 216, 459),\n",
       " (216, 405, 459),\n",
       " (368, 276, 460),\n",
       " (276, 368, 460),\n",
       " (380, 261, 461),\n",
       " (261, 380, 461),\n",
       " (336, 320, 464),\n",
       " (320, 336, 464),\n",
       " (372, 279, 465),\n",
       " (279, 372, 465),\n",
       " (416, 210, 466),\n",
       " (210, 416, 466),\n",
       " (432, 180, 468),\n",
       " (180, 432, 468),\n",
       " (376, 282, 470),\n",
       " (282, 376, 470),\n",
       " (396, 255, 471),\n",
       " (255, 396, 471),\n",
       " (456, 133, 475),\n",
       " (380, 285, 475),\n",
       " (285, 380, 475),\n",
       " (133, 456, 475),\n",
       " (420, 224, 476),\n",
       " (224, 420, 476),\n",
       " (405, 252, 477),\n",
       " (252, 405, 477),\n",
       " (384, 288, 480),\n",
       " (288, 384, 480),\n",
       " (480, 31, 481),\n",
       " (455, 156, 481),\n",
       " (444, 185, 481),\n",
       " (360, 319, 481),\n",
       " (319, 360, 481),\n",
       " (185, 444, 481),\n",
       " (156, 455, 481),\n",
       " (31, 480, 481),\n",
       " (418, 240, 482),\n",
       " (240, 418, 482),\n",
       " (483, 44, 485),\n",
       " (476, 93, 485),\n",
       " (388, 291, 485),\n",
       " (360, 325, 485),\n",
       " (325, 360, 485),\n",
       " (291, 388, 485),\n",
       " (93, 476, 485),\n",
       " (44, 483, 485),\n",
       " (480, 88, 488),\n",
       " (88, 480, 488),\n",
       " (392, 294, 490),\n",
       " (294, 392, 490),\n",
       " (480, 108, 492),\n",
       " (108, 480, 492),\n",
       " (475, 132, 493),\n",
       " (468, 155, 493),\n",
       " (435, 232, 493),\n",
       " (357, 340, 493),\n",
       " (340, 357, 493),\n",
       " (232, 435, 493),\n",
       " (155, 468, 493),\n",
       " (132, 475, 493),\n",
       " (456, 190, 494),\n",
       " (190, 456, 494),\n",
       " (396, 297, 495),\n",
       " (297, 396, 495),\n",
       " (480, 140, 500),\n",
       " (468, 176, 500),\n",
       " (400, 300, 500),\n",
       " (300, 400, 500),\n",
       " (176, 468, 500),\n",
       " (140, 480, 500)]"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pythagoricien(500)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "L’algorithme obtenu est en $\\mathcal{O}(n²)$"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "name": "presentation_complexite.py",
   "provenance": [],
   "version": "0.3.2"
  },
  "hide_input": false,
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}