Coma ben triar un juèc de cartas ?

Aqueu problèma de la vida vidanta apartene a la problematica generala de la triada, qu'es fòrça important en informatica. Donc l'informatica teorica a estudiat la cauva, e nos pòu dire quina es la melhora performança possibla d'un algoritme de triada, nos balhant d'exemples d'aquelei bòns algoritmes. Ai agut l'idèia de parlar d'aquò au vesent un amic triar de cartas embé una metòda siéuna : prim triar lei colors, puèi les numerò de cada color. En fach aquò es una aplicacion dau principi divisar per reinar, qu'es lo principi de basa de toei les bòns algoritmes. Aquò ven de l'observacion que triar dos paquets de 26 cartas es mai facil que triar un paquet de 52 cartas.

Ara vau pilhar dos exemples de triada e estudiar lei performanças de cadun. Farai una aplicacion a un juèc de 52 cartas monte nos cau una segonda per pilha cada carta o molon de cartas, e veiram lo temps totau que cau per cada metòda.

La metòda ninòia

 La solucion la plu simple es de cercar dins tot lo juèc per trobar l'as de còr, puèi tornar cercar dins la sòbra per trobar lo dos, etc. Per cada carta cau cercar un per un dins tot lo molon, ço que fa que cau prendre un nombre de cartes d'aperaqui 52 au carrat abanç d'aver un paquet de cartas triat. Lei informaticians teoricians dison que la complexitat de l'algoritme es d'òrdre O(n²).

Mai precisament per trobar l'as de còr fau manipular 52 cartas dins lo cas pejor, puèi per trobar lo dos cau manipular 51 cartas, etc. Lo nombre totau de cartas de manipular es donc la soma dei nombres de 1 fins a 52. Per l'anedòcta, aquela soma dei n premiers nombres foguèt carculada per Gauss a l'atge de onze ans, e es n(n+1)/2. Dins lo cas particular dau juèc de 52 cartas fa donc 52*(52+1)/2 = 1378. Embé una segonda per carta fa 22 minutas !

La triada fusion

Lei melhors algoritmas an una complexitat qu'es dicha d'òrdre O(n.log n), qu'es fòrça mai rapide per lei grandàs "juèc de cartas". Perque li a aquela fonccion matematica logaritme complicada ? Perque lo logaritme de basa p d'un nombre n es lo nombre de fes que podèm desseparar un ensèms de n elements en n parts fins a aver un solet element dins cada part (en imatge : a la drecha l'ensèms dau naut a n elements, e lo nombre de linhas es donada per lo logaritme).

L'idèia de la triada fusion es donc de desseparar lo juèc de carta en dos molons, puèi aplicar la triada fusion a cada molon (dison qu'es un algoritme recursiu), e fin finala fusionar de nòu lei dos molons en un solet. Per fusionar es simple : avèm dos molons de cartas, regarjam les cartas dau dessobre e pilham lo plu pichòta, la metèm dins lo tresen molon, e continuam fins que totei lei cartas siegan dins lo tresen molon..

Carculem lo temps necessari... Una manipulacion de cada molon per lei desseparar, la formula es soma per i=0..log₂(n)-1 de 2 poissança i (i es lo plan dins l'imatge, et 2 poissança i es lo nombre de molon a aquesto moment), ço que fa n, es a dire 52 (mai en fach fa 64 ja que cau aredonar lo logaritme). Puèi a cada plan de fusion una manipulacion per cada element, ço que fa n.log₂(n), es a dire 312. Au totau li a 376 operacions de faire, ço que fa 6 minutas e 16 segondas.

Va mièlhs, non ?

Comments

[lo_julien]

Adiéu,

En fach li a dos biais per mesurar la complexitat d'un algoritme : li a la complexitat mejana e la complexitat dins lo cas pejor. Co que carculi aqui es la complexitat dins lo cas pejor.

Ai pilhat d'exemples d'algoritmes monte la diferença es pas fòrça importanta : per exemple per la metòda ninòia la complexitat mejana es n(n+1)/4 mentre que la complexitat dins lo cas pejor es n(n+1)/2 , mai es totjorn en O(n²).

Li a d'autreis algoritmes monte aquò es pas parièr, per exemple lo mai emplegat dins la practica es la "triada rapida", qu'es fòrça efficace en generau, embé una complexitat mejana en O(n.log n), mai que degenera dins lo cas pejor en una complexitat O(n²). Embé de grands n la diferença pòu alora es fòrça importanta, e ai auvit qu'aquò es finda utilisat per d'hacker que balhan de cas pejor ai servidor per lei plantar.

[Clapassier de NY]

Adiussiatz,

Dins aqueste metoda ninoia, i a pas un element d'incertesa?
Per-eissemple, quora cercam lo dos dins los 51 cartas que demoran, podria esser la tresena carta. Auriam pas besonh de triar las 48 de mai.
A cada cop, l'esperada del nombre de cartas de triar pensi qu'es i/2. Que ne pensatz ?
Merces plan per aqueste charradissa plan interessanta.

Lo clapassier

[lo_julien]

En fach en començant en triant lei colors e en triant lei numeròs après fau 416 operacions, siá 6 minutas e 56 segonda. Adonc es pas lo melhor algoritme mai es pas marrit.
Aquò es perque 52 es encara un "pichòt" nombre, se li aviá 1000 cartas podriam rasonablament utilisar sonque d'algoritmes en O(n.ln n) coma la triada-fusion.