ALGORITMOS Y ESTRUCTURAS DE DATOS I – RESUMEN M1

ALGORITMOS Y TIEMPOS DE EJECUCION

Algoritmo: conjunto finito y ordenado de acciones con las que podemos resolver un
determinado problema. Son procedimientos computacionales que se encargan de tomar
las entradas, de procesarlas y generar una o varias salidas.

Diseño de algoritmos: es necesario conocer su contexto, de manera que se tenga claro su

alcance, sus datos de entrada y sus salidas. Se cuenta con tres recursos, que son: la
memoria, las operaciones aritméticas y las operaciones lógicas.

Análisis de Algoritmos: un problema puede solucionarse de más de una forma. Algunas

de estas serán más eficientes que otras (en el tiempo de ejecución, en el uso de los
recursos como la memoria, el disco, la red e, incluso, el tiempo que le lleva a un
desarrollador escribir el algoritmo).

A la hora de elegir un algoritmo para programar la funcionalidad de una aplicación, se

tendrán que tener en cuenta los parámetros, como el hardware sobre el que se ejecutará
dicha aplicación, la cantidad de datos que procesará y los tiempos de ejecución esperados
por el tipo de usuario al que está destinada.

Tipos de algoritmos (de mayor a menor eficiencia en tiempos de ejecución):

 Lineal: El tiempo de ejecución se incrementa a la misma velocidad en que se aumenta

la cantidad de datos de entrada. O sea, son directamente proporcionales a la cantidad
de datos de entrada a los que se someten. Es por esto que es el tipo de algoritmo más
eficiente.
 N*log(N): El logaritmo es una función que crece lentamente. Aunque crece más rápido
que la función lineal, es más lenta que la cuadrática y la cúbica. El tiempo de ejecución,
en estos algoritmos, es N veces el logaritmo de N, siendo N el tamaño de la entrada.
 Cuadrática: El tiempo de ejecución está definido por una función cuadrática (por
ejemplo, 3N2+2N+3) siendo N el tamaño de la entrada. Los algoritmos de este tipo son
menos eficientes que los del tipo N*Log(N).
 Cubica: El tiempo de ejecución está definido por una función cúbica (por ejemplo,
4N3+3N2+2N+3) siendo N el tamaño de la entrada. Están entre los menos eficientes, ya
que, ante pequeños incrementos en el tamaño de los datos, el tiempo de ejecución del
algoritmo crece rápidamente.

Pueden darse casos en que, por las constantes implicadas, una función N*Log(N) sea más
eficiente que una lineal. Sin embargo, ante una misma complejidad, las lineales son más
eficientes. Distinto es el caso de los algoritmos cuadráticos, que tienen altos tiempos de
ejecución, a partir de un tamaño de entrada de unos pocos miles. Peor aún, es el caso de
los algoritmos cúbicos que tienen tiempos de ejecución lentos, a partir de un tamaño de
entrada de unos pocos cientos.

La optimización del algoritmo es la tarea principal, a la hora de hacer que un código se

ejecute en forma eficiente, es decir, diseñar un buen algoritmo desde el principio. No
importa qué tanto se optimice el código. La optimización debe realizarse, primeramente,
sobre el algoritmo, porque es el que define la eficiencia en la ejecución.
 ALGORITMOS Y ESTRUCTURAS DE DATOS I – RESUMEN M1

NOTACION O Y ANALISIS
Notación O (Cota superior asintótica): proporciona una forma de conocer el
comportamiento de un algoritmo con base en los argumentos que le pasemos y su escala.
A medida que crecemos en el problema a resolver consideraremos a N tendiendo a
infinito (comportamiento asintótico).

Los algoritmos, ante entradas pequeñas, pueden mostrar una diferencia de eficiencia
mínima. No parece lógico realizar un gran esfuerzo por optimizar un algoritmo, ya que el
tiempo de ejecución mejorará muy poco con respecto a otro algoritmo más sencillo. Esas
situaciones no son tan comunes y en realidad, se necesitan algoritmos que funcionen
eficientemente ante las grandes entradas. Allí, las diferencias en el tiempo de ejecución
entre los algoritmos equivalentes, se hacen mayores. En estos casos sí se requiere
optimizar los algoritmos.

Lo que se busca es garantizar que el tiempo de ejecución de un algoritmo siempre sea

menor a una cota o límite superior. Con esto, se sabe que, en el peor de los casos, este
algoritmo tendrá un tiempo de ejecución que será proporcional a la función lineal N.

Lo importante en este tipo de análisis es poder encontrar una función que acote el
crecimiento que, en el peor de los casos, tendrá la complejidad del algoritmo.

Al conjunto de funciones que acotan dicho crecimiento lo llamamos O(g(x)) donde x

representa la cantidad de elementos que se van a procesar y g(x) es cualquier cota
superior de la función de complejidad del algoritmo.

Sea f(x) la función que expresa la complejidad de un algoritmo, entonces la expresión f(x)
pertenece a O(g(x)), significa que f(x) crece, a lo sumo, tan rápido como cualquiera de las
funciones g del conjunto O.

Por lo tanto, ahora se usará la O mayúscula para denotar aquella función que indique el
límite superior de crecimiento de una función. El orden será definido por el término más
importante de la función. Esto significa que, ante distintas funciones, se hará énfasis en el
término que le da el grado a la función analizada. Este término es el más dominante y
representa la tasa de crecimiento que interesa analizar.

Si se tiene una función cuadrática del tipo: 𝑎𝑁2+𝑏𝑁+𝑐 → orden cuadrático 𝑂(𝑁2) y que se
prescinde de los demás términos que son despreciables.

Los algoritmos polinomiales son “buenos” algoritmos y los algoritmos exponenciales son
“malos” algoritmos.

Si bien es de utilidad analizar el peor de los casos y conocer el límite superior (el cual no
será superado), también es útil, conocer el límite inferior (el mejor de los casos).
Asimismo, se puede querer expresar que una función tiene la misma tasa de crecimiento
que otra.

Notación Ω (Cota inferior asintótica): Si se dice que una función f(x) es Ω(g(x)), significa
que la función f(x) crecerá más lento o, a lo sumo, tan rápido como f(x).

Notación Θ (Cota ajustada asintótica): si se dice que una función f(x) es Θ(g(x)), significa
que la función f(x) tendrá la misma tasa de crecimiento que g(x).
 ALGORITMOS Y ESTRUCTURAS DE DATOS I – RESUMEN M1

A modo de conclusión, el análisis de los algoritmos es de vital importancia para poder

decidir, cuando se tienen varios algoritmos, cuál es el que más conviene, cuál es el mejor y
cuál se adecua mejor a las distintas necesidades. Asimismo, el análisis de los algoritmos
permite anticiparse y saber cuál será el comportamiento de un algoritmo en el peor de los
casos.
 ALGORITMOS Y ESTRUCTURAS DE DATOS I – RESUMEN M1

PROBLEMA DE LA BUSQUEDA ESTATICA

En el ámbito del software, una de las tareas más recurrentes es la que corresponde a la
búsqueda. El proceso de búsqueda puede efectuarse sobre una estructura ya ordenada o
sobre estructuras desordenadas. Además, en general, se asume que el elemento que se
quiere encontrar, existe.

Dado un entero X y una matriz A, devolver la posición de X en A o una indicación de que

no está presente. Si X aparece más de una vez, devolver cualquiera de las apariciones. La
matriz A nunca es modificada.

- Busqueda interna: elementos almacenados en la memoria (array).

- Busqueda externa: elementos almacenados en un dispositivo externo. La búsqueda se
realiza a través de un campo clave.

Buscar un determinado elemento, en un array o en un archivo, es encontrar la posición del

array o del archivo en que se encuentra almacenado ese elemento, o bien, detectar que
dicho elemento no pertenece al array o al archivo en el que se busca.

 METODOS

- Algoritmo de búsqueda secuencial: consiste en comparar cada elemento de una

estructura con el elemento que se quiere encontrar. Esto supone que no es necesario
tener una estructura ordenada. Al tener que transitar por todos los elementos, es
poco eficiente. Además, este algoritmo puede terminar en dos estados: con éxito (se
encontró el elemento buscado) o sin éxito (no se localizó el elemento buscado). La
mayoría de los algoritmos de búsqueda se basan en él.
En el peor de los casos, se tendrá que transitar por todos los elementos hasta llegar al
último. Por lo tanto, es de orden lineal O(n). Esto sucede tanto en un caso exitoso
(cuando el elemento buscado se encuentra y está en la última posición), como en un
caso sin éxito (cuando no se logra encontrar al elemento buscado y se tuvo que
recorrer toda la estructura). El mejor de los casos corresponde a encontrar el
elemento buscado en la primera posición.
En promedio, se podrá obtener un caso con éxito recorriendo la mitad de la
estructura, es decir, n/2, por lo que este algoritmo es de orden lineal O(n).

- Algoritmo de búsqueda binaria: parte de una estructura que está ordenada. Es un

algoritmo mucho más eficiente, debido a que va subdividiendo la estructura en
mitades hasta encontrar el elemento buscado o evidenciar que dicho elemento no se
encuentra. Este método está basado en la técnica divide y vencerás.

a) se comienza el proceso en el elemento central de la estructura (en caso de que la

cantidad de elementos sea impar) o casi central (en caso de que la cantidad de
elementos sea par).
b) se verifica si el elemento buscado corresponde al elemento central, en cuyo caso,
finaliza el proceso. En caso contrario, se corrobora si el elemento buscado es
mayor o menor a dicho elemento central. Si el elemento que se intenta hallar es
de mayor valor que el elemento central, se descarta la primera mitad. Si el
elemento que se busca es de menor valor que el elemento central, se descarta la
segunda mitad.
 ALGORITMOS Y ESTRUCTURAS DE DATOS I – RESUMEN M1

c) con la mitad no descartada, se comienza el proceso de nuevo, desde el primer

paso.

En el peor de los casos, se tienen dos situaciones:

1) se podrá conseguir un estado de éxito y encontrar al elemento buscado en la
última iteración. Se hará, por consiguiente, una cantidad de iteraciones igual a
Log(n). La última iteración corresponderá a un rango de un solo elemento.
2) se podrá conseguir un estado sin éxito, es decir, realizar todas las iteraciones y
detectar que no coinciden con el elemento buscado. Se harán, por consiguiente,
una cantidad de iteraciones igual a Log(n)+1. La última iteración corresponderá a
un rango nulo, es decir, no contendrá ningún elemento.

En promedio, se obtendrá al elemento buscado con una iteración menos que el peor
caso.

- Búsqueda por interpolación: es una alternativa cuando se presentan ciertas

situaciones particulares y ofrece, en promedio, un tiempo de ejecución mejor. Sin
embargo, en el peor de los casos, ofrecen un tiempo de ejecución bastante peor que
el de la búsqueda binaria. Por lo tanto, es importante detectar cuándo es realmente
ventajoso aplicar este método.
Se utiliza cuando acceder al elemento buscado es muy costoso (elemento almacenado
en un disco y no en memoria) y cuando los elementos están ordenados según una
distribución uniforme.

Limitación del análisis O: es muy efectivo pero su uso no es apropiado para entradas de
pequeño tamaño. Para este tipo de entradas, siempre es conveniente utilizar el algoritmo
más simple.
Las constantes de gran tamaño pueden entrar en acción cuando un algoritmo es
excesivamente complejo. También influyen, porque nuestro análisis no tiene en cuenta las
constantes y no puede, por lo tanto, diferenciar entre cosas como los accesos a memoria
(que son baratos) y los accesos a discos (que normalmente son varios miles de veces más
caros). Nuestro análisis asume que tenemos una memoria infinita, pero para las
aplicaciones que implican grandes conjuntos de datos, la falta de memoria suficiente
puede ser un grave problema.
Debemos hacer notar que no hemos tenido en cuenta elementos como el uso de la
memoria, dado que en nuestros análisis la consideramos como un recurso casi infinito.
Otro elemento que produce un impacto es, en aquellos algoritmos complejos, la influencia
de las constantes que, en nuestros casos, no son consideradas.
 ALGORITMOS Y ESTRUCTURAS DE DATOS I – RESUMEN M1

COMPLEJIDAD COMPUTACIONAL DE PROBLEMAS Y EL ANÁLISIS Y DISEÑO

DE ALGORITMOS
El objetivo de este tema es sentar las bases que permitan determinar qué algoritmo es
mejor (más eficiente) dentro de una familia de algoritmos que resuelven el mismo
problema. La eficiencia de un algoritmo se relaciona con la cantidad de recursos que
requiere para obtener una solución al problema (menor cantidad de recursos, mayor
eficiencia). Se asume que todos los algoritmos tratados van a ser eficaces, es decir,
resuelven adecuadamente el problema para el que se han diseñado.

A través de llamados al sistema operativo se puede conocer el valor del reloj de tiempo
real. Invocando al reloj, antes y después de realizar el algoritmo se tendrá una medida de
la duración del tiempo de ejecución. Sin embargo, esta medida es muy dependiente del
hardware (memoria, reloj, procesador), del sistema operativo (multitarea, multiusuario) y
puede variar significativamente dependiendo del computador, del compilador, y de la
carga del sistema. Al disponer de sistemas con multiprocesadores o que la ejecución sea
distribuida también afecta medir el tiempo con cronómetro.

Por la razón anterior como una medida del tiempo de ejecución, se considera contar las
instrucciones del lenguaje de alto nivel que son necesarias realizar.

Eficiencia algorítmica: La eficiencia de un algoritmo es determinada por el menor

consumo de recursos, como el tiempo y la memoria que se necesitan para que sea
ejecutado. Esta eficiencia se puede cuantificar con las siguientes medidas de complejidad:

- Complejidad temporal (tiempo de ejecución): tiempo empleado por éste para

ejecutarse y proporcionar un resultado a partir de los datos de entrada.
- Complejidad espacial: cantidad de memoria requerida (suma total del espacio que
ocupan las variables del algoritmo) antes, durante y después de su ejecución.

Estimar el coste de los algoritmos con independencia de los programas que los
implementen: para cada problema determinaremos una medida N, que llamaremos
tamaño de la entrada o número de datos a procesar por el programa.

Afecta al tiempo de ejecución, el orden en que se procesen los elementos de entrada.

Podría considerarse que los valores de los n casos que se presentan como entrada son los
correspondientes a un caso típico, a un caso promedio o a un caso de peor caso. El peor
caso es el más sencillo de definir (el que demore más para cualquier entrada); pero, si se
desea otros tipos de entrada, habría que definir qué se considera típico o la distribución
de los valores en el caso promedio.

Complejidad computacional: Un problema es un conjunto (posiblemente infinito) de

instancias junto con una pregunta sobre alguna propiedad de las instancias. Un algoritmo
es un proceso formal para encontrar la respuesta correcta a la pregunta de un problema
para una cierta instancia del problema.

 Problema: Problemas en general son conjuntos de instancias al cual corresponde un

conjunto de soluciones, junto con una relación que asocia para cada instancia del
problema un subconjunto de soluciones (posiblemente vacío).
 ALGORITMOS Y ESTRUCTURAS DE DATOS I – RESUMEN M1

Los dos tipos de problemas que estudiamos son los problemas de decisión y los
problemas de optimización. En los primeros, la respuesta es siempre “sı” o “no”,
mientras en la segunda clase de problemas la pregunta es del tipo “cuál es el mejor
valor posible” o “con qué configuración se obtiene el mejor valor posible”.

- Problema de decisión: En un problema de decisión, la tarea es decidir si o no la

relación entre instancias y soluciones asigna un subconjunto vacío a una dada
instancia. Si existen soluciones, la respuesta a la pregunta del problema es “si”, y si el
subconjunto es vacío, la respuesta es “no”.

- Problema de optimización: Para problemas de optimización, la instancia está

compuesta por un conjunto de configuraciones, un conjunto de restricciones, y
además una función objetivo que asigna un valor (real) a cada instancia. Si las
configuraciones son discretas, el problema es combinatorial.
La tarea es identificar cuál de las configuraciones factibles, es decir, las que cumplen
con todas las restricciones, tiene el mejor valor de la función objetivo. Depende del
problema si el mejor valor es el mayor (problema de maximización) o el menor
(problema de minimización). La configuración factible con el mejor valor se llama la
solución óptima de la instancia.

 Algoritmo: Un algoritmo es un método de solución para resolver una dada instancia de

un cierto problema. En computación, por lo general, se escribe el algoritmo en un
lenguaje de programación para ser ejecutado por una computadora.
Para un problema, por lo general existen varios algoritmos con diferente nivel de
eficiencia (es decir, diferente tiempo de ejecución con la misma instancia del
problema). En algoritmos deterministas, la salida del algoritmo depende únicamente
de la entrada de lo mismo, por lo cual se puede representar el algoritmo como una
función f : E → S. Existen también algoritmos probabilistas o aleatorizados donde éste
no es el caso.

 Calidad de Algoritmos: Las dos medidas más importantes de la calidad de un algoritmo

son

- el tiempo total de computación, medido por el número de operaciones de cómputo

realizadas durante la ejecución del algoritmo
- la cantidad de memoria utilizada

La notación para capturar tal información es a través de funciones de complejidad. Para

eliminar el efecto de una cierta computadora o un cierto lenguaje de programación, se
considera que el algoritmo se ejecuta en una máquina “modelo” virtual tipo RAM (inglés:
random access machine) que no tiene límite de memoria ni límite de precisión de
representación de números enteros o reales.

 Funciones de complejidad: Incluso si fijamos el tamaño de la instancia, todavía hay

variaciones en la cantidad de tiempo requerido para la ejecución del algoritmo. Por
ejemplo, es más difícil ordenar la lista [3, 5, 2, 9, 1] que la lista [1, 3, 5, 6, 7], como la
segunda ya está ordenada. Lo que queremos nosotros es tal caracterización de la
calidad de un algoritmo que nos facilita hacer comparaciones entre algoritmos. Las
soluciones incluyen el uso del caso peor, caso promedio y el caso amortizado.
 ALGORITMOS Y ESTRUCTURAS DE DATOS I – RESUMEN M1

- Función del peor caso: Formamos una función de complejidad f: Z+ → Z+ tal que para
un valor n, el valor f(n) representa el número de operaciones básicas para el más difícil
de todas las instancias de tamaño n. La única dificultad es identificar o construir la
instancia que es el peor posible para la ejecución del algoritmo.
- Funcion del caso promedio: Formamos una función de complejidad f: Z+ → R tal que
para un valor n, el valor f(n) representa el número promedio de operaciones básicas
sobre todas las instancias de tamaño n. Aquí la parte con posible dificultad es la
estimación de la distribución de probabilidad: ¿con que probabilidad ocurren
diferentes tipos de instancias? En práctica, si el peor caso es muy raro, resulta más útil
estudiar el caso promedio, si es posible…

 Clases de complejidad: Es posible definir diferentes tipos de clases de complejidad

computacional. Los requisitos para definir una clase son
- Fijar un modelo de computación (es decir, que tipo de máquina Turing se utiliza).
- La modalidad de computación: determinista, no determinista, etcétera.
- El recurso el uso del cual se controla por la definición: tiempo, espacio, etcétera.
- La cota que se impone al recurso (es decir, una función f correcta de complejidad).

Algoritmos tratables e intratables:

Clasificación de problemas: Los problemas matemáticos se pueden dividir en primera instancia

en dos grupos

- Problemas indecidibles: Aquellos que no pueden resolverse mediante un algoritmo.

- Problemas decidibles: Aquellos que cuentan con al menos un algoritmo para su
cómputo.

Sin embargo, que un problema sea decidible, no implica que se pueda encontrar su solución,
pues muchos problemas que disponen de algoritmos para su resolución son inabordables para
un computador por el elevado número de operaciones que hay que realizar para resolverlos.
Esto permite separar los problemas decidibles en dos:

- Intratables: Aquellos para los que no es factible obtener su solución.

- Tratables: Aquellos para los que existe al menos un algoritmo capaz de resolverlo en
un tiempo razonable.

Problemas intratables: los problemas denominados intratables son aquellos que, con entradas
grandes, no pueden ser resueltos por ningún computador, no importa lo rápido que sea,
cuanta memoria tenga o cuánto tiempo se le depara que lo resuelva. Lo anterior sucede debido
a que los algoritmos que existen para solucionar estos problemas tienen una complejidad muy
grande.