Complexité pratique contre complexité théorique - Historique des versions

Theo Connetable : /* Multiplication naive / Karatsuba */

2021-05-13T17:26:15Z

Multiplication naive / Karatsuba

← Version précédente		Version du 13 mai 2021 à 17:26
Ligne 187 :		Ligne 187 :
	L'algorithme de Karatsuba est un algorithme de type "diviser pour mieux régner" permettant de réduire le nombre de calcul lors de la multiplication de grands entiers de même taille.<br>		L'algorithme de Karatsuba est un algorithme de type "diviser pour mieux régner" permettant de réduire le nombre de calcul lors de la multiplication de grands entiers de même taille.<br>
	Dans un premier cas on observe si l'un des deux entiers a une taille de un, c'est à dire est un unique chiffre. Dans ce cas on applique tout simplement la multiplication dite naïve (chaque élément du nombre par le chiffre).<br>		Dans un premier cas on observe si l'un des deux entiers a une taille de un, c'est à dire est un unique chiffre. Dans ce cas on applique tout simplement la multiplication dite naïve (chaque élément du nombre par le chiffre).<br>
	Sinon, on sépare chacun des deux nombres en deux créant ~~quatres~~ nouveaux entiers "a", "b", "c" et "d".		Sinon, on sépare chacun des deux nombres en deux créant quatre nouveaux entiers "a", "b", "c" et "d".
	<pre>		<pre>
	Par exemple pour 1234 * 4567 on crée:		Par exemple pour 1234 * 4567 on crée:

Theo Connetable : /* medianes des medianes, quickselect */

2021-05-13T17:25:07Z

medianes des medianes, quickselect

← Version précédente		Version du 13 mai 2021 à 17:25
Ligne 180 :		Ligne 180 :
	[[Fichier:Tabnontri1000medpymedmedquick.PNG]]		[[Fichier:Tabnontri1000medpymedmedquick.PNG]]
	<br>Ces courbes représentent la comparaison de la complexité de la médiane python (en haut), de la médiane des médianes (au milieu) et du quickselect (en bas) afin de retrouver la valeur médiane d'un tableau non trié (sur 1000 essais). On peut voir que la complexité de la médiane des médianes et du quickselect ont une forme linéaire, <math>O(n)</math>. <br>		<br>Ces courbes représentent la comparaison de la complexité de la médiane python (en haut), de la médiane des médianes (au milieu) et du quickselect (en bas) afin de retrouver la valeur médiane d'un tableau non trié (sur 1000 essais). On peut voir que la complexité de la médiane des médianes et du quickselect ont une forme linéaire, <math>O(n)</math>. <br>
	On peut donc en conclure que d'un point de vue théorique les algorithmes de la médiane des médianes et du quick select sont à privilégiés, mais d'un point de vue pratique, la ~~mediane~~ de python prends beaucoup moins de temps à s'exécuter même pour des valeurs de tableaux élevés.<br>		On peut donc en conclure que d'un point de vue théorique les algorithmes de la médiane des médianes et du quick select sont à privilégiés, mais d'un point de vue pratique, la médiane de python prends beaucoup moins de temps à s'exécuter même pour des valeurs de tableaux élevés.<br>
	[[Fichier:Tabtri1000medpymedmedquick.PNG]]		[[Fichier:Tabtri1000medpymedmedquick.PNG]]
	<br>Ces courbes représentent la comparaison de la complexité de la médiane python (en haut), de la médiane des médianes (au milieu) et du quickselect (en bas) afin de retrouver la valeur médiane d'un tableau trié (sur 1000 essais).On remarque que d'un point de vu théorique, que le tableau soit trié ou non trié la complexité reste la même, mais d'un point de vu pratique on remarque que la médiane de python prend beaucoup moins de temps à s'exécuter sur un tableau déjà trié.		<br>Ces courbes représentent la comparaison de la complexité de la médiane python (en haut), de la médiane des médianes (au milieu) et du quickselect (en bas) afin de retrouver la valeur médiane d'un tableau trié (sur 1000 essais).On remarque que d'un point de vue théorique, que le tableau soit trié ou non trié la complexité reste la même, mais d'un point de vue pratique on remarque que la médiane de python prend beaucoup moins de temps à s'exécuter sur un tableau déjà trié.

	== Multiplication naive / Karatsuba ==		== Multiplication naive / Karatsuba ==

Theo Connetable : /* medianes des medianes, quickselect */

2021-05-13T17:23:56Z

medianes des medianes, quickselect

← Version précédente		Version du 13 mai 2021 à 17:23
Ligne 138 :		Ligne 138 :
	L'algorithme de la médiane des médianes est une variante de l'algorithme du quickselect où l'élément aléatoire du tableau est remplacé par la valeur médiane des différentes médianes des paquets de cinq éléments du tableau.		L'algorithme de la médiane des médianes est une variante de l'algorithme du quickselect où l'élément aléatoire du tableau est remplacé par la valeur médiane des différentes médianes des paquets de cinq éléments du tableau.
	Pour ce faire on sépare le tableau en paquets de cinq éléments. On crée ensuite un nouveau tableau comprenant les médianes des différents paquets. S'il n'y a qu'un élément au sein de ce tableau alors il s'agit de l'élément à appliquer au quickselect. Sinon on recommence l'opération avec ce nouveau tableau.		Pour ce faire on sépare le tableau en paquets de cinq éléments. On crée ensuite un nouveau tableau comprenant les médianes des différents paquets. S'il n'y a qu'un élément au sein de ce tableau alors il s'agit de l'élément à appliquer au quickselect. Sinon on recommence l'opération avec ce nouveau tableau.
	<br>'''~~Medianes~~ des ~~medianes~~ :'''		<br>'''Médianes des médianes :'''
	<pre>		<pre>
	def medianemediane(tab):		def medianemediane(tab):

Theo Connetable : /* medianes des medianes, quickselect */

2021-05-13T17:18:59Z

medianes des medianes, quickselect

← Version précédente		Version du 13 mai 2021 à 17:18
Ligne 108 :		Ligne 108 :
	== medianes des medianes, quickselect ==		== medianes des medianes, quickselect ==
	L'algorithme de Quickselect est un algorithme permettant de retrouver l'indice nième d’un tableau non trié. Pour cela on prend aléatoirement un élément du tableau et on le compare avec les autres éléments du tableau en créant ainsi deux nouveaux tableaux : les entier supérieurs et les entiers inférieurs à l'élément.<br>		L'algorithme de Quickselect est un algorithme permettant de retrouver l'indice nième d’un tableau non trié. Pour cela on prend aléatoirement un élément du tableau et on le compare avec les autres éléments du tableau en créant ainsi deux nouveaux tableaux : les entier supérieurs et les entiers inférieurs à l'élément.<br>
	Si l'indice recherché est supérieur ou égal à la taille des inférieurs et est inférieur à la taille du tableau moins la taille des supérieurs alors il s'agit de l'élément. Sinon, si l'indice est inférieur au tableau des éléments inférieurs on rappel la fonction avec cette fois ci en entrée le tableau des inférieurs et l'indice. Dans le dernier cas, on rappel la fonction avec en entrée le tableau des supérieurs et l'indice moins la taille du tableau auquel on a ajouté la taille des supérieurs.		Si l'indice recherché est supérieur ou égal à la taille des inférieurs et est inférieur à la taille du tableau moins la taille des supérieurs alors il s'agit de l'élément.<br>
			Sinon, si l'indice est inférieur au tableau des éléments inférieurs on rappel la fonction avec cette fois ci en entrée le tableau des inférieurs et l'indice. Dans le dernier cas, on rappel la fonction avec en entrée le tableau des supérieurs et l'indice moins la taille du tableau auquel on a ajouté la taille des supérieurs.

	<br>'''quickselect :'''		<br>'''quickselect :'''

Theo Connetable : /* medianes des medianes, quickselect */

2021-05-13T17:18:40Z

medianes des medianes, quickselect

← Version précédente		Version du 13 mai 2021 à 17:18
Ligne 107 :		Ligne 107 :

	== medianes des medianes, quickselect ==		== medianes des medianes, quickselect ==
	L'algorithme de ~~quickselect~~ est un algorithme permettant de retrouver l'indice nième ~~d'un~~ ~~tableaux~~ non trié. Pour cela on prend aléatoirement un élément du tableau et on le compare avec les autres éléments du tableau en créant ainsi deux nouveaux tableaux : les entier supérieurs et les entiers inférieurs à l'élément.<br>		L'algorithme de Quickselect est un algorithme permettant de retrouver l'indice nième d’un tableau non trié. Pour cela on prend aléatoirement un élément du tableau et on le compare avec les autres éléments du tableau en créant ainsi deux nouveaux tableaux : les entier supérieurs et les entiers inférieurs à l'élément.<br>
	Si l'indice recherché est ~~supérieure~~ ou égal à la taille des inférieurs et est inférieur à la taille du tableau moins la taille des supérieurs alors il s'agit de l'élément.		Si l'indice recherché est supérieur ou égal à la taille des inférieurs et est inférieur à la taille du tableau moins la taille des supérieurs alors il s'agit de l'élément. Sinon, si l'indice est inférieur au tableau des éléments inférieurs on rappel la fonction avec cette fois ci en entrée le tableau des inférieurs et l'indice. Dans le dernier cas, on rappel la fonction avec en entrée le tableau des supérieurs et l'indice moins la taille du tableau auquel on a ajouté la taille des supérieurs.

	Sinon, si l'indice est inférieur au tableau des éléments inférieurs on rappel la fonction avec cette fois ci en entrée le tableau des inférieurs et l'indice.
	Dans le dernier cas, on rapel la fonction avec en entrée le tableau des supérieurs et l'indice moins la taille du tableau auquel on a ajouter la taille des supérieurs.
	<br>'''quickselect :'''		<br>'''quickselect :'''
	<pre>		<pre>

Theo Connetable : /* Multiplication naive / Karatsuba */

2021-05-13T17:17:00Z

Multiplication naive / Karatsuba

← Version précédente		Version du 13 mai 2021 à 17:17
Ligne 299 :		Ligne 299 :
	return res		return res
	</pre>		</pre>
	[[Fichier:Kara1000.PNG]]		[[Fichier:Kara1000.PNG]]<br>
	On remarque donc que ces trois algorithmes ont une complexité linéaire, mais que la complexité l'algorithme de Karatsuba à trois appels récursifs croît beaucoup moins vite.		On remarque donc que ces trois algorithmes ont une complexité linéaire, mais que la complexité l'algorithme de Karatsuba à trois appels récursifs croît beaucoup moins vite.
	----		----

Theo Connetable : /* Multiplication naive / Karatsuba */

2021-05-13T17:16:31Z

Multiplication naive / Karatsuba

← Version précédente		Version du 13 mai 2021 à 17:16
Ligne 300 :		Ligne 300 :
	</pre>		</pre>
	[[Fichier:Kara1000.PNG]]		[[Fichier:Kara1000.PNG]]
			On remarque donc que ces trois algorithmes ont une complexité linéaire, mais que la complexité l'algorithme de Karatsuba à trois appels récursifs croît beaucoup moins vite.
	----		----
	CONNETABLE Theo (Tuteur : HYVERNNAT Pierre)		CONNETABLE Theo (Tuteur : HYVERNNAT Pierre)

Theo Connetable : /* Multiplication naive / Karatsuba */

2021-05-13T17:13:25Z

Multiplication naive / Karatsuba

← Version précédente		Version du 13 mai 2021 à 17:13
Ligne 299 :		Ligne 299 :
	return res		return res
	</pre>		</pre>
			[[Fichier:Kara1000.PNG]]
	----		----
	CONNETABLE Theo (Tuteur : HYVERNNAT Pierre)		CONNETABLE Theo (Tuteur : HYVERNNAT Pierre)

Theo Connetable : /* Multiplication naive / Karatsuba */

2021-05-13T17:13:01Z

Multiplication naive / Karatsuba

← Version précédente		Version du 13 mai 2021 à 17:13
Ligne 222 :		Ligne 222 :
	return res		return res
	</pre>		</pre>
	[[Fichier:~~Multnaive1000~~.~~PNG~~ ]]<br>		[[Fichier:Multinaive1000.png]]<br>
	On remarque la complexité de la multiplication naive : <math>(a * 10^{k} + b)(c*10^{k} + d)</math> est linéaire.		On remarque la complexité de la multiplication naive : <math>(a * 10^{k} + b)(c*10^{k} + d)</math> est linéaire.
	<br>'''Karatsuba à quatre appels récursifs:'''		<br>'''Karatsuba à quatre appels récursifs:'''

Theo Connetable : /* Multiplication naive / Karatsuba */

2021-05-13T17:11:42Z

Multiplication naive / Karatsuba

← Version précédente		Version du 13 mai 2021 à 17:11
Ligne 251 :		Ligne 251 :
	return (elmt110((taillenb1-1)2)) + ((elmt2 + elmt3) * 10**(taillenb1-1)) + elmt4		return (elmt110((taillenb1-1)2)) + ((elmt2 + elmt3) * 10**(taillenb1-1)) + elmt4
	</pre>		</pre>
			[[Fichier:Karanaive1000.PNG]]<br>
	La complexité de cet algorithme "karatsuba naïf est la même que la complexité de la multiplication "naïve".		La complexité théorique de cet algorithme "karatsuba naïf est la même que la complexité de la multiplication "naïve".
	<pre>		<pre>
	def karatsuba(nb1,nb2):		def karatsuba(nb1,nb2):

Complexité pratique contre complexité théorique - Historique des versions

Theo Connetable : /* Multiplication naive / Karatsuba */

Theo Connetable : /* medianes des medianes, quickselect */

Theo Connetable : /* medianes des medianes, quickselect */

Theo Connetable : /* medianes des medianes, quickselect */

Theo Connetable : /* medianes des medianes, quickselect */

Theo Connetable : /* Multiplication naive / Karatsuba */

Theo Connetable : /* Multiplication naive / Karatsuba */

Theo Connetable : /* Multiplication naive / Karatsuba */

Theo Connetable : /* Multiplication naive / Karatsuba */

Theo Connetable : /* Multiplication naive / Karatsuba */

Theo Connetable : /* Multiplication naive / Karatsuba */

Theo Connetable : /* medianes des medianes, quickselect */

Theo Connetable : /* medianes des medianes, quickselect */

Theo Connetable : /* medianes des medianes, quickselect */

Theo Connetable : /* medianes des medianes, quickselect */

Theo Connetable : /* Multiplication naive / Karatsuba */

Theo Connetable : /* Multiplication naive / Karatsuba */

Theo Connetable : /* Multiplication naive / Karatsuba */

Theo Connetable : /* Multiplication naive / Karatsuba */

Theo Connetable : /* Multiplication naive / Karatsuba */