UNIVERSIDAD AUTÓNOMA DEL CARIBE

INVESTIGACION
   

FACULTAD DE INGENIERÍA  
 

 
 
COMPLEJIDAD ALGORITMICA

 
INTEGRANTES 

NOMBRE CODIGO
1 JHORLIN ALVEAR ROA 251910027

2 JOHNATHAN GABRIEL 251910007

CASELLES NUÑEZ
3 NATALIA SOFIA ALGARIN 251910019
OROZCO

MAURICIO BARRIOS 
GRUPO D2
LABORATORIO DE PROGRAMACION II
BARRANQUILLA, ABRIL 28 DEL 2020
 ALGORITMO

En informática, un algoritmo es una secuencia de instrucciones secuenciales, gracias al cual pueden llevarse a

cabo ciertos procesos y darse respuesta a determinadas necesidades o decisiones. Se trata de conjuntos
ordenados y finitos de pasos, que nos permiten resolver un problema o tomar una decisión.

Los algoritmos no tienen que ver con los lenguajes de programación, dado que un mismo algoritmo o diagrama
de flujo puede representarse en diversos lenguajes de programación, es decir, se trata de un ordenamiento previo
a la programación.

Visto así, un programa no es otra cosa que una serie compleja de algoritmos ordenados y codificados mediante
un lenguaje de programación para su posterior ejecución en un computador.

CARACTERÍSTICAS DE UN ALGORITMO
Un algoritmo debe poseer las siguientes características:

 Precisión: Un algoritmo debe expresarse sin ambigüedad.

 Determinismo: Todo algoritmo debe responder del mismo modo antes las mismas condiciones.
 Finito: La descripción de un algoritmo debe ser finita.
CUALIDADES DE UN ALGORITMO
Un algoritmo debe ser, además:

 General: Es deseable que un algoritmo sea capaz de resolver una clase de problemas lo más amplia
posible.
 Eficiente: Un algoritmo es eficiente cuantos menos recursos en tiempo, espacio (de memoria) y
procesadores consume.
Por lo general es difícil encontrar un algoritmo que reúna ambas por lo que se debe alcanzar un compromiso que
satisfaga lo mejor posible los requisitos del problema.
COMPLEJIDAD ALGORITMICA
La complejidad algorítmica proporciona una noción matemática formal de la complejidad de la cadena. Sobre la
base de esto, se llega a las definiciones matemáticas 'estándar de oro' (aunque incuestionables) de aleatoriedad,
inducción, similitud e incluso inteligencia. Estas definiciones pueden convertirse en algoritmos prácticos
mediante el uso de compresores comunes para aproximar las soluciones universales. Se pueden considerar las
teorías como cognición idealizada con respecto a las cuales se puede tratar de describir la cognición biológica
real enumerando sesgos y limitaciones que deben definirse en relación con alguna referencia normativa. Esta es
una métrica teórica que nos ayuda a describir el comportamiento de un algoritmo en términos de tiempo de
ejecución (tiempo que tarda un algoritmo en resolver un problema) y memoria requerida (cantidad de memoria
necesaria para procesar las instrucciones que solucionan dicho problema). Esto nos ayuda a comparar entre la
efectividad de un algoritmo y otro, y decidir cuál es el que nos conviene implementar.
A la idea del tiempo de ejecución se le conoce como complejidad temporal, y a la idea de la memoria requerida
para resolver el problema se le denomina complejidad espacial. Dichos valores se encuentran en función del
tamaño del problema (valor o valores dictados por el número de elementos con los que un algoritmo trabaja),
aunque en algunos casos no. Por ejemplo, ¿tarda y consume lo mismo un algoritmo en ordenar cien o diez mil
elementos existentes en memoria? Obviamente que no. Por tanto, se habla de la complejidad algorítmica como
una función de valor n, y no como un valor en específico.
El enfoque más común para calcular la complejidad algorítmica de una cadena es el uso de algoritmos de
compresión que explotan las regularidades de la cadena y producen versiones comprimidas más cortas. La
longitud de una versión comprimida de una cadena es un límite superior de la complejidad algorítmica de la
cadena s .

En la práctica, es un problema conocido que no se pueden comprimir cadenas cortas, más cortas, por ejemplo,
que la longitud en bits del programa de compresión que se agrega a la versión comprimida de s , haciendo que el
resultado (el programa que produce s ) sea sensible a La elección del compresor y los parámetros
involucrados. Sin embargo, las cadenas cortas son a menudo el tipo de datos que se encuentran en muchos
entornos prácticos. Si bien el comportamiento asintótico de los compresores garantiza la convergencia eventual a
la complejidad algorítmica de s , gracias al teorema de la invariancia (que se enunciará más adelante), las
mediciones difieren considerablemente en el dominio de las cadenas cortas. Se han informado algunos intentos
para tratar este problema antes [20]

El resultado es un enfoque novedoso que proponemos para calcular numéricamente la complejidad de las
cadenas cortas como alternativa al método indirecto que utiliza algoritmos de compresión. El procedimiento
utiliza una combinación de resultados de áreas relacionadas de cómputo, como el concepto de probabilidad de
detención [3] , el problema de Busy Beaver [17] , la probabilidad algorítmica [18] , la semi-medida de Levin y el
teorema de codificación de Levin-Chaitin [11] , [12] .

CARACTERISTICAS DE LA COMPLEJIDAD ALGORITMICA.

• La complejidad algorítmica representa la cantidad de recursos (temporales) que necesita un algoritmo para
resolver un problema y por tanto permite determinar la eficiencia de dicho algoritmo.
• Los criterios que se van a emplear para evaluar la complejidad algorítmica no proporcionan medidas absolutas
sino medidas relativas al tamaño del problema.

COMPLEJIDAD ALGORITMICA.
CONCEPTOS BÁSICOS
• El tiempo empleado por el algoritmo se mide en pasos.
• El coste depende del tamaño de los datos.
• A la hora de evaluar el coste se debe de tener en consideración tres posibles casos:
– El coste esperado o promedio
– El coste mejor
– El coste peor
• Si el tamaño de los datos es grande lo que importa es el comportamiento asintótico de la eficiencia.

EL TIEMPO EMPLEADO POR EL ALGORITMO SE MIDE EN PASOS

• La medida del tiempo tiene que ser independiente: de la máquina, del lenguaje de programación, del
compilador y de cualquier otro elemento hardware o software que influya en el análisis.
Para conseguir esta independencia una posible medida abstracta puede consistir en determinar cuantos pasos se
efectúan al ejecutarse el algoritmo.

EL COSTE EN TIEMPO DEPENDE DEL TAMAÑO DE LOS DATOS

• El tiempo requerido por una algoritmo es función del tamaño de los datos.
• Por esta razón la complejidad temporal se expresa de la siguiente forma:
T(n)
• Dependiendo del problema, el tamaño del dato representa cosas diferentes:
– el número en sí
– el número de dígitos o elementos que lo compone.
• Otra característica importante es que no todos los datos, dentro de un problema, poseen la misma importancia
de cara a la complejidad algorítmica.

EL COSTE EN TIEMPO DEPENDE DEL TAMAÑO DE LOS DATOS

• Ejemplo 1: Algoritmo que determina la paridad de un
número restando 2 sucesivamente mientras el
resultado sea mayor que 1 para finalmente comprobar
el resultado.
– El problema tendrá n DIV 2 restas (depende de n).

• Ejemplo 2: Algoritmo de suma lenta

while b>0 do begin
a:=a+1;
b:=b-1;
end;
– En este caso T=T(b).
COMPLEJIDAD DE LOS ALGORITMOS
Cuando

hablamos de complejidad de los algoritmos hablamos principalmente de dos conceptos:

 La complejidad en si que es para un tamaño n tardará un tiempo y para un tiempo mayor cumplirá
f(n2) la complejidad nos describe el tipo de curva que cumplirá esa función f. Esto lo representamos como
O(f).

 El tiempo que tardará para un tamaño n es llamado tiempo de ejecución. Esto es lo representamos como

T(n).

PASOS PARA HALLAR LA COMPLEJIDAD DE UN ALGORITMO

Para enfocar la comparación de algoritmos seguiremos los siguientes pasos:

1. Averiguar la función f(n) que caracteriza los recursos requeridos por un algoritmo en función de tamaño
n de los datos a procesar.
 2. Dadas dos funciones f(n) y g(n) definir una relación de orden entre ellas que llamaremos complejidad y
que nos dirá cuándo una función es más compleja que la otra o cuándo son equivalentes.
3. Seleccionar una serie de funciones de referencia para situaciones típicas.
4. Definir conjuntos de funciones que llamaremos órdenes de complejidad.

Paso 1 – función característica

 Decidimos cómo medir N.

 Decidimos el recurso que nos interesa
 tiempo de ejecución = f(N)
 memoria necesaria = f(N)

A partir de aquí analizaremos f(n). la mayoría de las veces calcular la formula analítica es complicado por eso se
opta en solo conocer una cota superior, es decir, alguna función que se comporte "aún peor". De esta forma
podremos decir que el programa práctico nunca superará una cierta cota.

Paso 2 – complejidad

Dadas dos funciones f(n) y g(n) diremos que f(n) es más compleja que g(n) cuando

Diremos que f(n) es menos compleja que g(n) cuando

Y diremos que f(n) es equivalente a g(n) cuando

siendo K ≠0 y K ≠∞ Nótese que esta definición nos permite un análisis algorítmico conociendo la formulación
de la función, y también un análisis experimental observando los recursos consumidos para valores crecientes de
N.

Paso 3 – funciones de referencia

Se suelen manejar las siguientes

Paso 4 – órdenes de complejidad

A un conjunto de funciones que comparten un mismo comportamiento asintótico le denominaremos un orden de

complejidad. Habitualmente estos conjuntos se denominan O, existiendo una infinidad de ellos; pero nos
centraremos en unos pocos de uso frecuente.[ CITATION Alv \l 9226 ]

Ranking de complejidades

Existe una serie de complejidades que podemos denominar “típicas”. En la siguiente tabla las podemos ver
ordenadas de mejor a peor:

Propiedades fundamentales

Para poder calcular la complejidad de una función o método iterativo debemos aplicar las siguientes
propiedades:
 1. O(C·f) = O(f)

2. Regla de la suma: O(f 1 + f 2 ) = O(max(f 1 , f 2 )).

3. Regla del producto: O(f 1 ·f 2 ) = O(f 1 )·O(f 2 )

4. O(log a n) = O(log b n) = O(log n)

5. O(log(n K )) = O(K·log n) = O(log n)

6. O(log n·log n·…·log n) = O(log K n) ≠ O(log n)

REGLAS PRÁCTICAS
Aunque no existe una receta que siempre funcione para calcular la complejidad de un algoritmo, si es posible
tratar sistemáticamente una gran cantidad de ellos, basándonos en que suelen estar bien estructurados y siguen
pautas uniformes. Los algoritmos bien estructurados combinan las sentencias de alguna de las formas siguientes
Sentencias sencillas
Nos referimos a las sentencias de asignación, entrada/salida, etc. siempre y cuando no trabajen sobre variables
estructuradas cuyo tamaño esté relacionado con el tamaño N del problema. La inmensa mayoría de las sentencias
de un algoritmo requieren un tiempo constante de ejecución, siendo su complejidad O(1).
Secuencia (;)
La complejidad de una serie de elementos de un programa es del orden de la suma de las complejidades
individuales, aplicándose las operaciones arriba expuestas.
Decisión (if)
La condición suele ser de O(1), complejidad a sumar con la peor posible, bien en la rama THEN, o bien en la
rama ELSE. En decisiones múltiples (ELSIF, CASE), se tomará la peor de las ramas.
Bucles
En los bucles con contador explícito, podemos distinguir dos casos: que el tamaño N forme parte de los límites o
que no. Si el bucle se realiza un número fijo de veces, independiente de N, entonces la repetición sólo introduce
una constante multiplicativa que puede absorberse.
el bucle exterior se realiza N veces, mientras que el interior se realiza 1, 2, 3, ... N veces respectivamente. En
total, tenemos la suma de una serie aritmética:

1 + 2 + 3 + ... + N = N * (1+N) / 2  O (n2)

A veces aparecen bucles multiplicativos, donde la evolución de la variable de control no es lineal (como en los
casos anteriores)
Llamadas a procedimientos
La complejidad de llamar a un procedimiento viene dada por la complejidad del contenido del procedimiento en
sí. El coste de llamar no es sino una constante que podemos obviar inmediatamente dentro de nuestros análisis
asintóticos.
El cálculo de la complejidad asociada a un procedimiento puede complicarse notablemente si se trata de
procedimientos recursivos. Es fácil que tengamos que aplicar técnicas propias de la matemática discreta,
[ CITATION LGo82 \l 9226 ]

COMPLEJIDAD ALGORITMOS COMUNES

Ordenamiento burbuja

La Ordenación de burbuja funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente,
intercambiándolos de posición si están en el orden equivocado. Es necesario revisar varias veces toda la lista
hasta que no se necesiten más intercambios, lo cual significa que la lista está ordenada.

Mejor caso: 

Caso promedio: 
Peor caso:

Ordenamiento por selección

Consiste en encontrar el menor de todos los elementos del vector e intercambiarlo con el que está en la primera
posición. Luego el segundo más pequeño, y así sucesivamente hasta ordenarlo todo.[ CITATION lwh20 \l 9226 ]

complejidad

Búsqueda Lineal.
(A) MEJOR CASO: El algoritmo de búsqueda lineal termina tan pronto como encuentra el elemento buscado en
el array. Si tenemos suerte, puede ser que la primera posición examinada contenga el elemento que buscamos, en
cuyo caso el algoritmo informará que tuvo éxito después de una sola comparación. Por tanto, la complejidad en
este caso será O(1).
(B) PEOR CASO: Sucede cuando encontramos X en la última posición del array. Como se requieren n
ejecuciones del bucle mientras, la cantidad de tiempo es proporcional a la longitud del array n, más un cierto
tiempo para realizar las instrucciones del bucle mientras y para la llamada al método. Por lo tanto, la cantidad de
tiempo es de la forma an + b (instrucciones del mientras * tamaño del arreglo + llamada al método) para ciertas
constantes a y b, que representan el coste del bucle mientras y el costo de llamar el método respectivamente.
Representando esto en notación O, O(an+b) = O(n).
(C) CASO MEDIO: Supongamos que cada elemento almacenado en el array es igualmente probable de ser
buscado. La media puede calcularse tomando el tiempo total de encontrar todos los elementos y dividiéndolo por
n:
Total = a (1 + 2 + ...+n) + bn = a (n(n+1) / 2) + bn, a representa el costo constante asociado a la ejecución del
ciclo y b el costo constante asociado a la evaluación de la condición. 1, 2 , ..n, representan el costo de encontrar
el elemento en la primera, segunda, ..., enesima posición dentro del arreglo.
Media = (Total / n) = a((n+1) / 2) + b que es O(n).
Este es el algoritmo de más simple implementación pero no el más efectivo. En el peor de los casos se recorre el
array completo y el valor no se encuentra o se recorre el array completo si el valor buscado está en la última
posición del array. La ventaja es su implementación sencilla y rápida, la desventaja, su ineficiencia.

Búsqueda binaria

Para poder medir la velocidad de cálculo del algoritmo de búsqueda binaria, se deberán obtener el número de
comparaciones que realiza el algoritmo, es decir, el número de vueltas del ciclo o el número de recursiones.
Aunque en principio puede parecer que ambas versiones invierten el mismo tiempo, la recursiva es más lenta a
medida que se incrementa considerablemente el número de elementos a considerar, ya que existirán más
llamadas a la función por resolver, con el consiguiente gasto de tiempo y memoria en guardar y restaurar
parámetros.

En el mejor caso, la búsqueda binaria podría toparse con el elemento buscado en el primer punto medio,
requiriéndose sólo una comparación de elementos. Esto equivale al caso óptimo durante una búsqueda
secuencial, pero en el peor de los casos la búsqueda binaria es mucho más rápida cuando N es grande.

El algoritmo de búsqueda binaria progresivamente va disminuyendo el número de elementos sobre el que

realizar la búsqueda a la mitad: n, n/2, n/4, ... Así, tras log (n) divisiones se habrá localizado el elemento o se
tendrá la seguridad de que no estaba. Log (n) divisiones es el numero máximo de veces que se puede reducir a la
mitad la cantidad de registros a considerar, hasta que solo se tenga un elemento.[ CITATION art20 \l 9226 ]

CONCLUSIÓN
En conclusión, la complejidad algorítmica o ritmo de crecimiento es una métrica que te permite como
programador evaluar la factibilidad de las diferentes soluciones de un problema, y poder decidir con un
argumento matemático cuál es mejor mediante comparaciones.
Este tipo de herramienta teórica tiene aparentemente poca utilidad en el día a día de un programador habitual,
pues requiere de algoritmos mucho más complejos y pilas de datos muy grandes, y a menos que trabajes con Big
Data, Machine Learning o hardware con recursos muy limitados como Arduino donde la optimización es crucial,
la complejidad algorítmica tiene poca importancia a nivel práctico. Sin embargo, es un concepto bastante básico
e importante de conocer, pues te permite dimensionar y pensar acerca del comportamiento de tus soluciones y la
manera en la que los solucionas, y no solo codear un algoritmo que termine costándote más en un futuro.

Referencias

[1] J. Alvarez, «Complejidad Algoritmica,» Universidad de Valladolid, Valladolid.

[2] J.-P. DelahayE y H. Zenil , «Numerical evaluation of algorithmic complexity for short strings: A glance into
the innermost structure of randomness,» Applied Mathematics and Computation, vol. 219, nº 1, pp. 66-
67, 2012.

[3] M. Hutter y P. Sunehag, International Encyclopedia of the Social & Behavioral Sciences (Second Edition),
James D. Wright, 2015.

[4] M. E. Raffino, «Concepto.de,» Concepto.de, 11 Enero 2019. [En línea]. Available:

 https://concepto.de/algoritmo-en-informatica/. [Último acceso: 27 Abril 2020].

[5] F. J. G. Gala, «Rootear,» Rootear, 3 Diciembre 2014. [En línea]. Available:

https://rootear.com/desarrollo/complejidades-algoritmos. [Último acceso: 27 Abril 2020].

[6] J. Guillermo, «Medium,» Medium, 22 Junio 2018. [En línea]. Available:

https://medium.com/@joseguillermo_/qu%C3%A9-es-la-complejidad-algor%C3%ADtmica-y-con-qu
%C3%A9-se-come-2638e7fd9e8c. [Último acceso: 27 Abril 2020].

[7] Wikipedia, «wikipedia,» Wikipedia, 31 Octubre 2019. [En línea]. Available:

https://es.wikipedia.org/wiki/Eficiencia_algor%C3%ADtmica. [Último acceso: 27 Abril 2020].

[8] R. M. P. López, «Monografias,» Monografias, [En línea]. Available:

https://www.monografias.com/trabajos27/complejidad-algoritmica/complejidad-algoritmica.shtml.
[Último acceso: 27 Abril 2020].

[9] J. A. Jimenez, «Grupo de Lógica Computacional,» Universidad de Sevilla, [En línea]. Available:
http://www.cs.us.es/~jalonso/cursos/i1m/temas/tema-28.html. [Último acceso: 27 Abril 2020].

[10] J. A. Mañas, «Análisis de Algoritmos – Complejidad,» 2017.