Tecnológico Nacional de México

Instituto Tecnológico de Tijuana

SUBDIRECCIÓN ACADÉMICA

DEPARTAMENTO DE SISTEMAS Y COMPUTACIÓN

SEMESTRE FEBRERO 2021 – JUNIO 2021

Ingeniería en Sistemas Computacionales

Materia: Estructura de Datos 6SC3A

Unidad 1 – Introducción a la Estructura de Datos

Nombre del Alumno: Osorio Cuevas Daniel Alejandro #2021607

Nombre del Maestro(a): Claudia Negrete Sánchez

Fecha de Entrega: 11 de marzo de 2021

 Índice
Introducción ........................................................................................................................................ 3
Notación O Grande ............................................................................................................................. 3
Complejidad en el tiempo ................................................................................................................... 5
Complejidad en el espacio................................................................................................................... 5
Eficiencia de los algoritmos ................................................................................................................ 6
CALCULO DE LA EFICIENCIA DE UN ALGORITMO ............................................................ 7
PRINCIPIO DE INVARIANZA ..................................................................................................... 7
MEJOR, PEOR Y TIEMPO MEDIO .............................................................................................. 7
OPERACIONES ELEMENTALES ................................................................................................ 7
Conclusión........................................................................................................................................... 8
Fuentes Bibliográficas ......................................................................................................................... 8

2|Page
 Introducción
En la investigación que se realizara se indagaran los diferentes aspectos mas relevantes e
importantes sobre el análisis de algoritmos, notación o grande, complejidad de espacio, de
tiempo y la eficiencia de los algoritmos; las características mas importantes para determinar
un algoritmo acorde a nuestras necesidades, como normalmente nosotros a lo que conocemos
un algoritmo es el proceso o los pasos que se realizan para poder realizar o solucionar alguna
problemática como por ejemplo cuando se pincha una llanta de tu automóvil, usas algoritmos
para poder realizar el cambio de la misma, esto es muy parecido a lo que se realiza en
programación ya que los programas que se realizan se ejecutan por procesos o pasos lo que
es la entrada de datos, el procedimiento o procesos que se realizan con ellos y la salida que
es lo que se muestra en la pantalla, por ejemplo un mensaje o un resultado.

Notación O Grande
Se utiliza para hacer referencia a la velocidad de crecimiento de los valores de una función,
es decir su utilidad radica en encontrar un límite superior de tiempo de ejecución de un
algoritmo en el peor de los casos. La definición de esta notación es la siguiente:
g(n) O(F(n)) si y solo si existen las constantes C y n tales que g(n) <= C * F(n).
para todo C>=n se tiene que T(n)<=Cn el orden de la magnitud de una función es el orden
del término de la función más grande en términos de n.
Características:
• El análisis de algoritmos estima el consumo de recursos de un algoritmo.
• Esto nos permite comparar los costos relativos de dos o más algoritmos para resolver
el mismo problema.
• El análisis de algoritmos también les da una herramienta a los diseñadores de
algoritmos para estimar si una solución propuesta es probable que satisfaga las
restricciones de recursos de un problema.
• El concepto de razón de crecimiento es la razón a la cual el costo de un algoritmo
crece conforme el tamaño de la entrada crece.
• Usualmente se mide el tiempo de ejecución de un algoritmo, y el almacenamiento
primario y secundario que consume.
• Consideración principal para estimar el desempeño de un algoritmo, es el número de
operaciones básicas requeridas por el algoritmo para procesar una entrada de cierto
tamaño.

3|Page
A la hora de realizar un análisis teórico de algoritmos es común calcular su complejidad en
un sentido asintótico, es decir, para un tamaño de entrada suficientemente grande. La cota
superior asintótica, y las notaciones omegas (cota inferior) y theta (caso promedio) se usan
con esa finalidad. Por ejemplo, la búsqueda binaria decimos que se ejecuta en una cantidad
de pasos proporcional a un logaritmo, en O(log(n)), coloquialmente "en tiempo logarítmico".
Normalmente las estimaciones asintóticas se utilizan porque diferentes implementaciones del
mismo algoritmo no tienen por qué tener la misma eficiencia. No obstante, la eficiencia de
dos implementaciones "razonables" cualesquiera de un algoritmo dado están relacionadas
por una constante multiplicativa llamada constante oculta.
La medida exacta (no asintótica) de la eficiencia a veces puede ser computada, pero para ello
suele hacer falta aceptar supuestos acerca de la implementación concreta del algoritmo,
llamada modelo de computación. Un modelo de computación puede definirse en términos de
un ordenador abstracto, como la Máquina de Turing, y/o postulando que ciertas operaciones
se ejecutan en una unidad de tiempo. Por ejemplo, si al conjunto ordenado al que aplicamos
una búsqueda binaria tiene n elementos, y podemos garantizar que una única búsqueda
binaria puede realizarse en un tiempo unitario, entonces se requieren como mucho log2 N +
1 unidades de tiempo para devolver una respuesta.
Las medidas exactas de eficiencia son útiles para quienes verdaderamente implementan y
usan algoritmos, porque tienen más precisión y así les permite saber cuánto tiempo pueden
suponer que tomará la ejecución. Para algunas personas, como los desarrolladores de
videojuegos, una constante oculta puede significar la diferencia entre éxito y fracaso. Las
estimaciones de tiempo dependen de cómo definamos un paso. Para que el análisis tenga
sentido, debemos garantizar que el tiempo requerido para realizar un paso esté acotado
superiormente por una constante. Hay que mantenerse precavido en este terreno; por ejemplo,
algunos análisis cuentan con que la suma de dos números se hace en un paso. Este supuesto
puede no estar garantizado en ciertos contextos. Si por ejemplo los números involucrados en
la computación pueden ser arbitrariamente grandes, dejamos de poder asumir que la adición
requiere un tiempo constante (usando papel y lápiz, compara el tiempo que necesitas para
sumar dos enteros de 2 dígitos cada uno y el necesario para hacerlo con enteros de 1000
dígitos).

4|Page
 Complejidad en el tiempo
Denominado de manera coloquial como el número de pasos en relación con la longitud
realizados, el número de comparaciones entre enteros, el numero de veces en que un
bucle interno es ejecutado, o alguna otra u ni d a d natural relación a d a al tiempo real
total, que el algoritmo va a tomar. Una medida que suele ser útil conocer es el tiempo de
ejecución de un programa en función de N, lo que denominaremos T(N).
Esta función se puede medir físicamente (ejecutando el programa, reloj en mano), o
calcularse sobre el código contando instrucciones a ejecutar y multiplicando por el tiempo
requerido por cada instrucción.
Así, un trozo sencillo de programa como:
S1; for (int i= 0; i < N; i++) S2.

Requiere:
T(N)= t1 + t2*N
Siendo t1 el tiempo que lleve ejecutar la serie “S1” de sentencias, y t2 el que lleve la serie
“S2”. Prácticamente todos los programas reales incluyen alguna sentencia condicional,
haciendo que las sentencias efectivamente ejecutadas dependan de los datos concretos que se
le presenten. Esto hace que más que un valor T(N) debamos hablar de un rango de valores:
Tmin(N) ⇐ T(N) ⇐ Tmax(N)
Los extremos son habitualmente conocidos como “caso peor” y “caso mejor”. Entre ambos
se hallará algún “caso promedio” o más frecuente. Cualquier fórmula T(N) incluye
referencias al parámetro N y a una serie de constantes “Ti” que depende de factores externos
al algoritmo como pueden ser la calidad del código generado por el compilador y la velocidad
de ejecución de instrucciones del ordenador que lo ejecuta.
Dado que es fácil cambiar de compilador y que la potencia de los ordenadores crece a un
ritmo vertiginoso (en la actualidad, se duplica anualmente), intentaremos analizar los
algoritmos con algún nivel de independencia de estos factores; es decir, buscaremos
estimaciones generales ampliamente válidas.

Complejidad en el espacio
Denominado de manera coloquial como el número de espacios de almacenamiento en
relación con la longitud de entrada. Se acostumbra a mencionar memoria “extra” necesaria,
sin contar la memoria necesitada para almacenar a la entrada misma. Es la memoria que
utiliza un programa para su ejecución; es decir el espacio de memoria que ocupan todas las
variables propias del algoritmo.
Esta se divide en Memoria Estática y Memoria Dinámica.
• Memoria estática. Para calcularla se suma de memoria que ocupan las variables
declaradas en el algoritmo.

5|Page
 • Memoria dinámica. Su cálculo no es tan simple ya que depende de cada ejecución del
algoritmo.
Ejemplo: algoritmo de búsqueda en árboles.
Función búsqueda árboles.
Devuelve una solución o fallo.
Inicializa un árbol de búsqueda con estado inicial.
Bucle hacer
o Si no hay candidatos para expandir.
o Entonces devolver fallo.
o En otro caso escoger nodo para expandir.
o Si el nodo es el objetivo.
o Entonces devolver solución.
o En otro caso expandir nodo.

M = profundidad máxima del árbol (puede ser infinita)

D = profundidad de la mejor solución (menor costo)
B = factor de ramificación (número máximo de sucesiones) = 10
Depth Nodes Time Memory
0 1 1 millisecond 100 bytes
2 111 .1 second 11 Kb
4 11111 11 second 1Mb
6 10^6 18 minutes 111 Mb

Eficiencia de los algoritmos

Medida del uso de los recursos computacionales requeridos por la ejecución de un algoritmo
en función del tamaño de las entradas.
T(n): Tiempo empleado para ejecutar el algoritmo con una entrada de tamaño n.
El análisis de algoritmos es una parte importante de la Teoría de Complejidad computacional
más amplia, que provee estimaciones teóricas para los recursos que necesita cualquier
algoritmo que resuelva un problema computacional dado. Estas estimaciones resultan ser
bastante útiles en la búsqueda de algoritmos eficientes.
A la hora de realizar un análisis teórico de algoritmos es común calcular su complejidad en
un sentido asintótico, es decir, para un tamaño de entrada suficientemente grande. La Cota
superior asintótica y las notaciones omega (cota inferior) y theta (caso promedio) se usan con
esa finalidad. Por ejemplo, la búsqueda binaria decimos que se ejecuta en una cantidad de
pasos proporcional a un logaritmo, en O(log(n)), coloquialmente “en tiempo logarítmico”.
6|Page
Normalmente las estimaciones asintóticas se utilizan porque diferentes implementaciones del
mismo algoritmo no tienen por qué tener la misma eficiencia. No obstante, la eficiencia de
dos implementaciones “razonables” cualesquiera de un algoritmo dado están relacionadas
por una constante multiplicativa llamada constante oculta. La medida exacta (no asintótica)
de la eficiencia a veces puede ser computada, pero para ello suele hacer falta aceptar
supuestos acerca de la implementación concreta del algoritmo, llamada modelo de
computación. Un modelo de computación puede definirse en términos de un ordenador
abstracto, como la Máquina de Turing, y/o postulando que ciertas operaciones se ejecutan en
una unidad de tiempo. Por ejemplo, si al conjunto ordenado al que aplicamos una búsqueda
binaria tiene ‘n’ elementos, y podemos garantizar que una única búsqueda binaria puede
realizarse en un tiempo unitario, entonces se requieren como mucho log2 N + 1 unidades de
tiempo para devolver una respuesta.
Las medidas exactas de eficiencia son útiles para quienes verdaderamente implementan y
usan algoritmos, porque tienen más precisión y así les permite saber cuánto tiempo pueden
suponer que tomará la ejecución. Para algunas personas, como los desarrolladores de
videojuegos, una constante oculta puede significar la diferencia entre éxito y fracaso.
CALCULO DE LA EFICIENCIA DE UN ALGORITMO
✏ Método empírico o a posteriori: Se programa el algoritmo y se evalúa en un número
grande de casos en los que se mide el tiempo de ejecución.

✏ Método teórico o a priori: Se mide su rapidez antes de programarlo mediante

herramientas matemáticas. Expresar el tiempo como una función del tamaño de los casos
considerados.
PRINCIPIO DE INVARIANZA
Dado un algoritmo y dos implementaciones suyas I1 e I2, que tardan T1(n) y T2(n) segundos
respectivamente, el Principio de Invarianza afirma que existe una constante real c > 0 y un
número natural n0 tales que para todo n >= n0 se verifica que T1(n) <= cT2(n).
Es decir, el tiempo de ejecución de dos implementaciones distintas de un algoritmo dado no
va a diferir más que en una constante multiplicativa.
MEJOR, PEOR Y TIEMPO MEDIO
El comportamiento de un algoritmo puede cambiar notablemente para diferentes entradas (lo
ordenados que se encuentren ya los datos a ordenar). Se Estudian tres casos:
1. Caso peor: mayor número posible de instrucciones ejecutadas por el algoritmo.
2. Caso mejor: menor número posible de instrucciones ejecutadas por el algoritmo.
3. Caso medio (o general): número de instrucciones igual a la esperanza matemática de
la variable aleatoria definida por todas las posibles trazas del algoritmo para un
tamaño de la entrada dado, con las probabilidades de que éstas ocurran para esa
entrada.
OPERACIONES ELEMENTALES
A la hora de medir el tiempo, siempre se hará en función del número de operaciones

7|Page
elementales que realiza dicho algoritmo, entendiendo por operaciones elementales (OE)
aquellas que el computador realiza en tiempo acotado por una constante.

Asignaciones a variables de tipo predefinido por el compilador.

• Los saltos (llamadas a funciones y procedimientos, retornos desde ellos, etc.)

• Las comparaciones lógicas y el acceso a estructuras indexadas básicas, como lo son
los vectores y matrices.

El tiempo de ejecución de un algoritmo depende en el conjunto de instrucciones, la velocidad

del procesador, la velocidad I/O del disco, etc. Por lo tanto, se estima la eficiencia de un
algoritmo de manera asintótica. Por lo general se acostumbra a estimar la eficiencia en
cuestión de tiempo donde dicha función de tiempo es representada como T (n) donde n es el
tamaño de la entrada. Existen distintas notaciones asintóticas usadas para calcular la
complejidad de tiempo de un algoritmo dado.

Conclusión
Como se expuso, estas características mencionadas expanden más allá de la comprensión de
un conjunto de pasos ordenados los cuales (en la vida cotidiana) no acostumbramos a razonar
más allá de que se necesita y que resultado nos deja. Esta información es sumamente
relevante para que se empiece a razonar de una forma mas objetiva y eficiente para la
redacción de un código para crear estándares de industria, así como una mayor eficiencia de
ejecución y un mejor aprecio a la planeación de los mismos.
Como opinión, el general he comprendido más la notación asintótica lo cual de alguna
manera nos ayudara mas adelante como una herramienta que se ha estado desarrollando a lo
largo de la carrera estudiantil.

Fuentes Bibliográficas
http://jitorres.blogspot.com/2011/11/notacion-o-
grande.html#:~:text=Definicion%3A,el%20peor%20de%20los%20casos.&text=El%20an%
C3%A1lisis%20de%20algoritmos%20estima%20el%20consumo%20de%20recursos%20d
e%20un%20algoritmo.
https://itslr.edu.mx/archivos2013/TPM/temas/s3u7.html
http://estructura-de-datos-itsav.blogspot.com/2012/03/13-complejidad-algoritmo.html
https://jorgeantilefblog.wordpress.com/eficiencia-de-algoritmos-2/

8|Page