fundamento de programación

Estructura de datos

 

Complejidad
 

 
En
 
 general,
 es
 posible
 realizar
 el
 estudio
 de
 la
 complejidad
 de
 un
 algoritmo
 sólo en
 
base
 a
 un
 conjunto
 reducido
 de
 sentencias,
 aquellas
 que
 caracterizan
 que
 el
 algoritmo
 
sea
 lento
 o
 rápido
 en
 el sentido
 que
 nos
 interesa.
 

 La
 eficiencia
 de
 un
 algoritmo
 es
 una
 medida
 de
 lo
 que
 consume
 a
 la
 hora
 de
 
ejecutarse: tiempo
 de
 ejecución,
 y
 memoria
 ocupada.
 

 
Para
 medirlos
 una
 forma
 sería
 la
 empírica:
 cronometrar
 el
 tiempo
 y
 analizar el
 uso
 de
 
memoria,
 pero
 esto
 nos
 daría
 el
 resultado
 para
 un
 caso
 concreto
 en
 un
 PC
 concreto,
 y
 
de
 poco
 nos sirve
 esto.
 Una
 medida
 más
 util
 es
 el
 orden
 de
 complejidad
 del
 algoritmo,
 
que
 es
 la
 base
 del
 análisis
 de
 los
 mismos. 

 
El
 orden
 de
 complejidad
 (o
 complejidad
 asintótica)
 se
 expresa
 usando
 la
 notación
 
"O(n)",
 que
 nos
 dice
 como
 se relaciona
 el
 tiempo
 de
 ejecución
 con
 el
 tamaño
 de
 la
 
entrada.
 

 

 

 

 
Eficiencia
 

 
En
 general,
 se
 considera que
 la
 solución
 de
 un
 problema
 es
 eficiente
 si
 el
 tiempo
 de
 
ejecución
 está
 acotado
 por
 una
 función
 polinomial,
 es
 decir, por
 O(nk).
 A
 este
 tipo
 de
 
se
 le
 considera
 un
 problema
 fácil.
 En
 caso
 de
 que
 su
 tiempo
 de
 ejecución
 sea...