Anàlisi d'algorismes
L'anàlisi d'algorismes és una part important de la teoria de complexitat computacional més àmplia, que proveeix estimacions teòriques per als recursos que necessita qualsevol algorisme que resolgui un problema computacional donat. Aquestes estimacions resulten ser bastant útils en la recerca d'algorismes eficients.
A l'hora de realitzar una anàlisi teòrica d'algorismes és comú calcular la seva complexitat en un sentit asimptòtic, és a dir, per una mida d'entrada prou gran. La cota superior asimptòtica, i les notacions omega i theta s'usen amb aquesta finalitat. Per exemple, la cerca binària diem que s'executa en una quantitat de passos proporcional a un logaritme, en O (log (n)), col·loquialment "en temps logarítmic". Normalment les estimacions asimptòtiques s'utilitzen perquè diferents implementacions del mateix algorisme no tenen per què tenir la mateixa eficiència. No obstant l'eficiència de dues implementacions "raonables" qualssevol d'un algorisme donat estan relacionades per una constant multiplicativa trucada constant oculta.
La mesura exacta (no asimptòtica) de l'eficiència de vegades pot ser computada però per a això sol fer falta acceptar supòsits sobre la implementació concreta de l'algorisme, anomenada model de computació. Un model de computació pot definir en termes d'un ordinador abstracte, com la Màquina de Turing, i/o postulant que certes operacions s'executen en una unitat de temps. Per exemple, si al conjunt ordenat al que apliquem una cerca binària té n elements, i podem garantir que una única cerca binària pot realitzar en un temps unitari, llavors es requereixen com molt log 2 N+1 unitats de temps per tornar una resposta.
Les mesures exactes d'eficiència són útils per als qui veritablement implementen i fan servir algoritmes, perquè tenen més precisió i així els permet saber quant temps poden suposar que prendrà l'execució. Per a algunes persones, com els desenvolupadors de videojocs, una constant oculta pot significar la diferència entre èxit i fracàs.
Les estimacions de temps depenen de com definim un pas. Perquè l'anàlisi tingui sentit, hem de garantir que el temps requerit per realitzar un pas estigui acotat superiorment per una constant. Cal mantenir previngut en aquest terreny, per exemple, algunes anàlisis compten que la suma de dos nombres es fa en un pas. Aquest supòsit pot no estar garantit en certs contextos. Si per exemple els nombres involucrats en la computació poden ser arbitràriament grans, deixem de poder assumir que l'addició requereix un temps constant (usant paper i llapis, compara el temps que necessites per sumar dos enters de 2 dígits cadascun i el necessari per fer-ho amb enters de 1000 dígits).
Vegeu també
[modifica]Bibliografia
[modifica]- Thomas H. Corman, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. Chapter 1: Foundations, pp.3-122.ISBN 0-262-03293-7.
- Fonaments d'algorísmia. Gilles Brassard & Paul Bratley ISBN 84-89660-00-X