Estructura De Datos

 

       

 Departament de Llenguatges i Sistemes Informàtics, FIB­UPC    

ANÁLISIS DE LA EFICIENCIA DE LOS  ALGORITMOS 

 Anàlisi i Disseny d’Algorismes ‐ ADA

María Teresa Abad Soriano  Curso 2010/2011   

 

Anàlisi i Disseny d’Algorismes – ADA  FIB – UPC, curs 2010/2011 

 

       Análisis de la eficiencia de los algoritmos 

 

 

CONTENIDOS 
 
 

1. JUSTIFICACIÓN ................................................................................................................ 3  .
1.1.  1.2.  Factores determinantes ................................................................................................ 3  Una manera de medir ................................................................................................... 5 2.  NOTACIONES ASINTÓTICAS ........................................................................................ 8 
2.1.  2.2.  Definiciones .................................................................................................................. 9  Propiedades ................................................................................................................ 10  .

3.  TASAS DE CRECIMIENTO HABITUALES ................................................................ 11  4.  CÁLCULO DEL COSTE DE UN ALGORITMO ITERATIVO ................................... 12  5.  CÁLCULO DEL COSTE DE ALGUNOS ALGORITMOS RECURSIVOS ................. 17 
5.1.  5.2. Los teoremas maestros ............................................................................................... 18  Otros métodos ............................................................................................................ 19 

6.  REFRESCO  MATEMÁTICO ......................................................................................... 20 
6.1.  6.2.  6.3. Inducción ..................................................................................................................... 20  Exponenciación y logaritmos....................................................................................... 22  Series ........................................................................................................................... 22 

7. FUENTES ......................................................................................................................... 24 

 

 

 
María Teresa Abad                         Departament Llenguatges i Sistemes Informàtics   

2                                           

Anàlisi i Disseny d’Algorismes – ADA  FIB – UPC, curs 2010/2011 

 

       Análisis de la eficiencia de los algoritmos 

 

 
     

1. JUSTIFICACIÓN 
  La  tarea  de  la  programación consiste,  entre  otras  muchas  cosas,  en  la  confección  de  un  algoritmo o programa que resuelva satisfactoriamente el problema planteado. Es evidente que  la  corrección  es  la  condición  indispensable  que  debe  satisfacer  un    algoritmo,  es  decir,  que  haga exactamente lo que se espera de él.  Existen una seria de características adicionales que permiten establecer el nivel de calidad del algoritmo: legibilidad, modificabilidad, modularidad,  reusabilidad, portabilidad, etc.   Pero para que sea definitivamente satisfactorio nos conviene que resuelva el problema lo más  rápido posible o que use la menor cantidad de memoria posible o, mejor aún, ambas cosas a la  vez.  Por  tanto  es  necesario  poder  medir  el  consumo  de  recursos,  tiempo  y  memoria,  de  un programa para establecer su nivel de calidad. Además esta información será útil para efectuar  comparaciones  entre  diferentes  alternativas  que  resuelvan  el  mismo  problema  y  permitirá  seleccionar la mejor opción, aquella que menos recursos consuma.  Este tema se centra en el  estudio del consumo de recursos de un algoritmo, y que comúnmente denominamos el análisis ...