Anàlisis d'algoritmes

Archiu:Binary search vs Linear search example svg.svg

Figura 1: En la figura es mostra la comparació de passos realisats pels algoritmes de busca llineal i la busca binaria, representats en magenta i cian, respectivament. En l'eixemple, abdós algoritmes s'utilisen per a buscar l'entrada "Morin, Arthur" en una llista ordenada de 33 noms. Com la busca llineal ignora l'orde de la llista pren 28 passos per a trobar l'entrada, mentres que, la busca binaria ho fa en 5 passos ya que aprofita l'orde de les entrades.

El terme anàlisis d'algoritmes va ser falcat per Donald Knuth^[1] i es referix al procés de trobar la complexitat computacional d'un algoritme que resolga un problema computacional dau, en l'objectiu de proveir estimacions teòriques dels recursos que necessita. Usualment, els recursos als quals es fa referència són el temps (complexitat temporal) i l'almagasenament (complexitat espacial). Mentres que la complexitat temporal involucra determinar una funció que relaciona la llongitut o el tamany de l'entrada de l'algoritme en el número de passos que realisa, la complexitat espacial busca la cantitat d'ubicacions d'almagasenament que utilisa. Distints algoritmes poden utilisar-se per a resoldre un mateix problema i a la seua volta els algoritmes poden estudiar-se de forma independent del llenguage de programació a utilisar i de la màquina a on s'eixecutarà.^[2] Açò significa que es necessiten tècniques que permeten comparar l'eficiència dels algoritmes abans de la seua implementació.

Anàlisis de la complexitat temporal

Este anàlisis és conegut també en el nom d'anàlisis del temps d'eixecució. A continuació, es presenta una explicació intuïtiva utilisant l'eixemple del algoritme de busca para després profundisar en forma més teòrica.

Punt de vista intuïtiu

Si es pensa en el problema de trobar una clau en un conjunt de registres ubicats dins d'un vector tornant la posició a on es troba, es tenen distints algoritmes de busques que es poden aplicar. El més senzill és la busca seqüencial pero si el conjunt d'elements es troben ordenats (segons la seua clau) dins del vector es podria aplicar la busca binaria. D'este eixemple es poden traure vàries conclusions.

Per un costat, depenent l'algoritme utilisat el procés de busca serà més o menys eficient en el sentit de cantitat de comparacions realisades. Per eixemple, segons la Figura 1 per a buscar "Morin, Arthur" la busca seqüencial deu realisar 28 comparacions mentres que la busca binaria realisa solament 5 comparacions. Açò confirma que per a la resolució d'un determinat problema existix més d'un algoritme i que estos solen tindre distints nivells d'eficiència, necessitant-se una forma d'elegir-los abans de programar-los com es va mencionar en l'introducció.

Si es continua analisant la busca seqüencial i si l'intenció és trobar a "Zeeman, Pieter" es deuen realisar 33 comparacions pero si s'intenta trobar a "Abt, Antal" solament dos comparacions són necessàries. És dir, si es busca l'últim element la cantitat de comparacions és equivalent a n, a on n és la cantitat d'elements presents en el vector; pero per un atre, també depén de la clau a buscar. En conseqüència, la cantitat de comparacions necessàries depén de la cantitat d'elements que posseïxca el vector i la seua orde; i de l'element a buscar, açò és, depén de les entrades de l'algoritme. D'ací es pot concloure que per a analisar el temps d'eixecució es podria contar la cantitat de comparacions realisades i li la multiplica pel temps requerit per cada comparació.

Pero ací es presenta un atre inconvenient ¿el temps que pren una comparació depén de la computadora en a on s'estiga eixecutant? Seria convenient trobar una funció que donat el tamany d'entrada acote els passos realisats per l'algoritme per a trobar la solució en un temps que depenga d'una constant C que representa el temps en diferents computadores.

Anàlisis dels distints casos

Archiu:Peor-Promedio-mejor.png

Figura 2: Representació gràfica dels tres casos analisats dins de la complexitat temporal d'un algoritme.

Diferents entrades de la mateixa llongitut poden causar que l'algoritme es comporte distint, per lo que es podria analisar l'algoritme des de tres perspectives: el millor cas, el cas promig i el pijor cas.^[3] En la Figura 2 es mostra dits casos de manera gràfica.

Millor cas: és la funció definida pel número mínim de passos donats en qualsevol instància de tamany n. Representa la curva més baixa en el gràfic (vert) i es denomina cota inferior.

Case promig: és la funció definida pel número promig de passos donats en qualsevol instància de tamany n.

Pijor cas: és la funció definida pel número màxim de passos donats en qualsevol instància de tamany n. Açò representa la curva que passa pel punt més alt en el gràfic (roig) i es denomina cota superior.

Quan no s'especifica lo contrari, la funció que descriu el rendiment d'un algoritme sol este cas, ya que este cas garantisa que l'algoritme no tardarà major cantitat de temps, és dir acota superiormente la cantitat de passos.

Punt de vista teòric

Anàlisis asintòtic

A l'hora de realisar un anàlisis teòric d'algoritmes és comú calcular la seua complexitat en un sentit asintòtic, és dir, per a un tamany d'entrada suficientment gran. La cota superior asintòtica, i les notacions omega (cota inferior) i theta (case promig) s'usen en eixa finalitat. Per eixemple, la busca binaria diem que s'eixecuta en una cantitat de passos proporcional a un logaritmo, en $O (l o g (n))$ , coloquialmente "en temps logarítmic". Normalment, les estimacions asintòtiques s'utilisen perque diferents implementacions del mateix algoritme no tenen per qué tindre la mateixa eficiència. No obstant, l'eficiència de dos implementacions "raonables" qualssevol d'un algoritme donat estan relacionades per una constant multiplicativa cridada constant amagada.

Órdens de creiximent

Artícul principal → Cota superior asintòtica.

Archiu:Comparison computational complexity.svg

Figura 3: Gràfic que mostra les funcions comunament utilisades en l'anàlisis d'algoritmes representant el número d'operacions N versus el tamany d'entrada n.

De manera informal, es pot dir que un algoritme exhibix una taxa de creiximent de l'orde d'una funció matemàtica si més allà d'un cert tamany d'entrada $n$ , la funció $f (n)$ multiplicada per una constant positiva proporciona un llímit superior o llímit per al temps d'eixecució d'eixe algoritme. En atres paraules, per a un tamany d'entrada donat n major que algun $n_{0}$ i una constant $c$ , el temps d'eixecució d'eixe algoritme mai serà major que $f (n)$ . Este concepte s'expressa en freqüència utilisant la notació O Gran, que brinda una forma convenient d'expressar el pijor dels casos per a un algoritme donat.

Per eixemple, l'ordenament per inserció creix cuadráticamente a mida que aumenta el seu tamany d'entrada, llavors es pot dir que este tipo d'ordenament és de l'orde de n quadrat, en notació O Gran seria: $O (n^{2})$ . Un atre tipo de funcions que poden ser utilisades per a acotar un algoritme són les mostrades en la Figura 3.

Anàlisis no asintòtic

La mida exacta (no asintòtica) de l'eficiència a voltes pot ser computada, pero per a això sol fer falta acceptar suposts sobre l'implementació concreta de l'algoritme, cridada model de computació. Un model de computació pot definir-se en térmens d'un ordenador abstracte, com la Màquina de Turing, i/o postulant que certes operacions s'eixecuten en una unitat de temps. Per eixemple, si al conjunt ordenat al que apliquem una busca binaria té $n$ elements, i podem garantisar que una única busca binaria pot realisar-se en un temps unitari, llavors es requerixen, com a molt, $l o g_{2} N + 1$ unitats de temps per a tornar una resposta.

Les mides exactes d'eficiència són útils per a els qui verdaderament implementen i usen algoritmes perque tenen més precisió i, aixina, els permet saber quànt temps poden supondre que prendrà l'eixecució. Per a algunes persones, com els desenrolladors de videojocs, una constant amagada pot significar la diferència entre èxit i fracàs.

Les estimacions de temps depenen de cóm definim un pas. Per a que l'anàlisis tinga sentit, devem garantisar que el temps requerit per a realisar un pas es troba acotat superiormente per una constant. Cal mantindre's precavido en este terreny; per eixemple, alguns anàlisis conten en que la suma de dos números es fa en un pas. Este supòsit pot no estar garantisat en certs contexts. Si, per eixemple, els números involucrats en la computació poden ser arbitrariamente grans, deixem de poder assumir que l'adició requerix un temps constant (usant paper i llapis, compara el temps que necessites per a sumar dos sancers de 2 dígits cada u i el necessari per a fer-ho en dos sancers pero de 1000 dígits cada u).

Rellevància

En la pràctica l'anàlisis d'algoritmes és important perque l'us accidental o no intencional d'un algoritme ineficiente pot afectar significativament el rendiment d'un sistema. En aplicacions de temps real, un algoritme que tarda massa en eixecutar-se pot fer que els seus resultats siguen obsolets o inútils. Un algoritme ineficiente també pot terminar requerint una cantitat antieconòmica de potència de càlcul o almagasenament per a funcionar, tornant-ho pràcticament inútil.

Vore també

Referències

↑ (1997) The Art of Computer Programming, Estats Units: Addison-Wesley.
↑ The Algorithm Design Manual, Second edició, Springer International Publishing, pp. 742. ISBN 978-1-84800-069-8.
↑ (1996) An Introduction to the Analysis of Algorithms, Estats Units: Addison-Wesley.

Bibliografia

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 1: Foundations, pp.3–122.
Gilles Brassard & Paul Bratley. Fonaments de algoritmia. (ISBN 84-89660-00-X)
Greene, Daniel A.; Knuth, Donald E. (1982). Mathematics for the Analysis of Algorithms (Second ed.). Birkhäuser. ISBN 3-7643-3102-X.

Referències

Este artícul conté una traducció derivada de «Análisis de algoritmos» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[1] (1997) The Art of Computer Programming, Estats Units: Addison-Wesley.

[2] The Algorithm Design Manual, Second edició, Springer International Publishing, pp. 742. ISBN 978-1-84800-069-8.

[3] (1996) An Introduction to the Analysis of Algorithms, Estats Units: Addison-Wesley.

[1]

[2]

[3]