Resumen de estructura-1-28-2-28

Vista previa del material en texto

Contenido 
1.1 Clasificación de la estructura de datos. ................................................................... 3 
1.2 Tipos Abstractos de datos (TAD´s) .............................................................................. 6 
1.3 Ejemplos de TDA ......................................................................................................... 9 
1.4 Memoria Estática ....................................................................................................... 11 
1.4 Memoria dinámica ..................................................................................................... 13 
1.5 Análisis de algoritmos ................................................................................................ 24 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1.1 Clasificación de la estructura de datos. 
 
¿Qué es una estructura de datos? 
Forma particular de organizar datos en una computadora para que pueda ser utilizado 
de manera eficiente. Diferentes tipos de estructuras de datos son adecuados para diferentes 
tipos de aplicaciones, y algunos son altamente especializados para tareas específicas. 
 
Tipos de estructura de datos. 
Arrays. La estructura de datos más simple es el array lineal (o unidimensional). Un array 
lineal es una lista de números finitos de datos similares, referenciados por medio de un 
conjunto de n números consecutivos, normalmente 1,2,3, …, n. 
Pila. Una pila, también denominada sistema último-dentro primero-fuera (LIFO), es una lista 
lineal en la cual las inserciones y extracciones tienen lugar sólo por un extremo llamado 
cúspide. 
Cola. Una cola, también denominada sistema primero-dentro primero-fuera (FIFO), es una 
lista lineal en la cual las extracciones se realizan siempre por un extremo llamado frente y las 
inserciones por el extremo contrario llamado final de la lista. 
Grafos. Los datos contienen, en algunos casos, relaciones entre ellos que no es 
necesariamente jerárquica. Por ejemplo, supongamos que unas líneas aéreas realizan vuelos 
sólo entre ciudades conectadas por líneas. La estructura de datos que refleja esta relación 
recibe el nombre de grafo. 
 
 
Operaciones con estructuras de datos. 
 
Recorrido. Implica el acceder a cada registro una única vez, aunque uno o más ítems del 
registro sean procesados. (Este acceso o procesamiento también se denomina a veces por el 
término «visitar» el registro). 
Búsqueda. Implica la localización de un registro caracterizado por una determinada clave o 
también el acceso a todos los registros que cumplan una o más condiciones. 
Inserción. Cuando añadimos nuevos registros a la estructura. 
Eliminación. Operación de borrado de un registro de la estructura. 
Ordenación. Es la operación de clasificar los registros conforme a un orden lógico 
determinado (por ejemplo, alfabéticamente, de acuerdo a una clave de nombre, o numérica, 
de acuerdo a alguna clave de número, tal como número de Seguridad Social o de inventario). 
Mezcla. Es la operación de combinar dos archivos previamente ordenados en uno único que 
también lo está. 
 
 
 
 
 
 
 
Estructuras lógicas de datos: Las estructuras de datos lógicas son aquellas en que 
cada variable pertenece a alguna estructura de datos explícita o implícitamente definida, la 
cual determinará el conjunto de operaciones válidas para ella. Además, cada estructura de 
datos lógicas puede tener varias representaciones físicas diferentes para sus 
almacenamientos. 
Estructuras de datos primitivas y simples: Se dicen que son primitivas a aquellas 
que no están compuestas por otras estructuras de datos, algunos ejemplos de estos pueden ser 
enteros, booleanos, entre algunos caracteres. Algunas otras estructuras de datos son las que 
están formadas por estas estructuras de datos primitivas, un claro ejemplo que tenemos es las 
estructuras de datos simples, algunos ejemplos que tenemos de este tipo de estructura de 
datos son: cadenas, arreglos y registros. 
Estructuras de datos lineales y no lineales: La estructura de datos lineales es un 
tipo de estructura en donde los elementos de datos se ordenan secuencial o linealmente donde 
los elementos se adjuntan a su anterior y siguiente adyacente en lo que se llama estructura de 
datos lineal. En este tipo de estructura de datos vamos a contar con un solo nivel, por lo tanto, 
podremos atravesar todos los elementos de esta de una sola vez, cosa que no pasa con los no 
lineales, otro punto importante a mencionar es que estas son muy fáciles de implementar en 
las computadoras. 
Ejemplos de estas pueden ser: 
Matriz, pila, cola, etc. 
Estructuras de datos no lineales: Las estructuras de datos no lineales son aquellas 
en donde los elementos no están organizados de forma secuencial, en está no existe un único 
nivel por lo que su implementación es mucho más difícil atravesar todos sus elementos de 
una sola vez, su implementación es más compleja que la estructura lineal. 
Ejemplos de esta estructura puede ser: 
Árboles y grafos. 
1.2 Tipos Abstractos de datos (TAD´s) 
Un TAD se define como una estructura algebraica compuesta por un conjunto de 
objetos abstractos que modelan elementos del mundo real, y un conjunto de operaciones para 
su manipulación. 
Un TAD es un ente cerrado y autosuficiente, que no requiere de un contexto 
específico para que pueda ser utilizado en un programa. Esto garantiza portabilidad y 
reutilización del software. 
Las partes que forman un TAD son: 
a) atributos (tipos de datos, identificadores, etc.) 
b) funciones (rutinas) que definen las operaciones válidas para manipular los datos 
(atributos). 
A la forma de operar y encerrar los atributos y funciones dentro un TAD se le 
denomina encapsulamiento. 
Para implementar un TAD se siguen dos pasos: 
1. Diseñar las estructuras de datos que van a representar cada objeto abstracto. 
2. Desarrollar una función, por cada operación del TAD, que simule el comportamiento del 
objeto abstracto, sobre las estructuras de datos seleccionadas. 
Las operaciones de un TAD se clasifican en 3 grupos, según su función sobre el objeto 
abstracto: 
a) Constructora: es la operación encargada de crear elementos del TAD. 
b) Modificadora: es la operación que puede alterar el estado de un elemento de un TAD. 
c) Analizadora: es una operación que no altera el estado del objeto, sino que tiene como 
misión consultar su estado y retornar algún tipo de información. 
Entre las aplicaciones de los TAD’s se encuentran el TAD lista, el TAD pila, el TAD cola, 
etc. 
TAD´s Estática 
La creación y mantenimiento de un TAD estático requiere de memoria no dinámica, 
es decir, el espacio en memoria para almacenar los datos es reservado en tiempo de 
compilación (Arreglos). 
TAD’s Dinámicos (Asignación dinámica de memoria). 
La creación y mantenimiento de estructuras dinámicas de datos (TAD’s dinámicos), 
requiere de obtener más espacio de memoria (reservar memoria) en tiempo de ejecución para 
almacenar datos o para almacenar el tipo de clase “Nodo”. 
El TAD Lista 
Una lista está formada por una serie de elementos llamados nodos los cuales son 
objetos que contiene como variable miembro un puntero asignado y variables de cualquier 
tipo para manejar datos. El puntero sirve para enlazar cada nodo con el resto de nodos que 
conforman la lista. De esto podemos deducir que una lista enlazada (lista) es una secuencia 
de nodos en el que cada nodo esta enlazado o conectado con el siguiente (por medio del 
puntero mencionado anteriormente). El primer nodo de la lista se denomina cabeza de la lista 
y el último nodo cola de la lista. Este último nodo suele tener su puntero igualado a NULL 
Para indicar que es el fin de la lista. 
 
 
 
 
 
 
El TAD pila 
Una pila(stack) es una secuencia de cero o más elementos de un mismo tipo, que 
puede crecer y decrecer por uno de sus extremos (el tope dela pila). 
 
 
 
Las pilas se denominan también estructuras LIFO (Last In First Out), porque principal 
es que el último elemento en llegar es el primero en salir. Son muy utilizadas en 
programación para evaluar expresiones. En todo momento, el único elemento visible de la 
estructura es el último que se colocó. Se define el tope de la pila como el punto donde se 
encuentra dicho elemento, y el fondo, como el punto donde se encuentra el primer elemento 
incluido en la estructura. 
En el TAD pila se definen operaciones constructoras para crear la pila, operaciones 
modificadoras para agregar y eliminar elementos y analizadoras para retornar el elemento del 
tope de la lista, las cuales serán analizadas más adelante. 
 
 
 
 
1.3 Ejemplos de TDA 
Ejemplo: implementación de pilas a través de TDA. 
 
Ejemplo: Implementación de listas a través de TDA. 
 
 
 
 
 
 
Ejemplo: implementación de estáticos a través de TDA. 
 
 
Ejemplo: implementación de dinámicos a través de TDA. 
 
 
 
 
 
 
 
 
 
 
 
1.4 Memoria Estática 
¿Qué es memoria? 
Es un espacio lógico para guardar información. 
La memoria (también llamada almacenamiento) se refiere a parte de los 
componentes que forman parte de una COMPUTADORA, Son dispositivos que retienen 
DATOS informáticos durante algún intervalo de tiempo. Las memorias de computadora 
proporcionan unas de las principales funciones de la computación moderna, la retención o 
almacenamiento de información. Es uno de los componentes fundamentales de todas las 
computadoras modernas que, acoplados al CPU. 
¿QUÉ ES ESTÁTICA? 
La forma más fácil de almacenar el contenido de una variable en memoria en tiempo 
de ejecución es en memoria estática o permanente a lo largo de toda la ejecución del 
programa. O sea, que no se modifica al menos en tiempo de ejecución. 
No todos los objetos (variables) pueden ser almacenados estáticamente. 
Para que un objeto pueda ser almacenado en memoria estática su tamaño (número de 
bytes necesarios para su almacenamiento) ha de ser conocido en tiempo de compilación, 
como consecuencia de esta condición no podrán almacenarse en memoria estática: 
¿Qué es dinámica? 
Su tamaño puede variar durante la ejecución del programa y puede ser liberado 
mediante la función free. O sea que se modifica permanentemente. 
Memoria estática.- 
Las técnicas de asignación de memoria estática son sencillas. 
La asignación de memoria puede hacerse en tiempo de compilación y los objetos están 
vigentes desde que comienza la ejecución del programa hasta que termina. 
En los lenguajes que permiten la existencia de subprogramas, y siempre que todos los 
objetos de estos subprogramas puedan almacenarse estáticamente se aloja en la memoria 
estática un registro de activación correspondiente a cada uno de los subprogramas. 
Estos registros de activación contendrán las variables locales, parámetros formales y 
valor devuelto por la función. 
 
Consideraciones 
 
ü Error en tiempo de ejecución de índice fuera del rango. 
ü Se debe conocer con anticipación el tamaño de la estructura. 
ü Se guardan en memorias adyacentes. 
ü Vectores, matrices, cubos, registros, archivos. 
 
Ventajas 
· La velocidad de acceso es alta. 
· Para retener los datos solo necesita estar energizada. 
· Lógica simple. 
 
Desventajas: 
ü No se puede modificar el tamaño de la estructura en tiempo de ejecución. 
ü No es óptimo con grandes cantidades de datos. 
ü Desperdicio de memoria cuando no se utiliza en su totalidad del tamaño v[100] . 
ü Menor capacidad, debido a que cada celda de almacenamiento requiere más transistores. 
ü Mayor costo por bit. 
ü Mayor consumo de Potencia 
 
 
 
 
 
 
 
 
 
1.4 Memoria dinámica 
 
Tipos de datos en memoria 
 
Datos estáticos: Su tamaño y forma es constante durante la ejecución de un 
programa y por tanto se determinan en tiempo de compilación. El ejemplo típico son los 
arrays. Tienen el problema de que hay que dimensionar la estructura de antemano, lo que 
puede conllevar desperdicio o falta de memoria. 
 
Datos dinámicos: Su tamaño y forma es variable en caso de ser necesario a lo largo 
de un programa, por lo que se crean y destruyen en tiempo de ejecución. Esto permite 
dimensionar la estructura de datos de una forma precisa: se va asignando memoria en 
tiempo de ejecución según se va asignando. 
 
¿Qué es la memoria dinámica? 
La memoria dinámica se refiere a aquella memoria que no puede ser definida ya que 
no se conoce o no se tiene idea del número de la variable a considerarse, la solución a este 
problema es la memoria dinámica que permite solicitar memoria en tiempo de ejecución, 
por lo que cuanta más memoria se necesite, más se solicita al sistema operativo. 
 
El sistema operativo maneja la memoria gracias al uso de punteros, por la misma 
naturaleza del proceso nos impide conocer el tamaño de la memoria necesaria en el 
momento de compilar. 
 
La memoria dinámica es un espacio de almacenamiento que se puede solicitar en 
tiempo de ejecución. Además de solicitar espacios de almacenamiento, también podemos 
liberarlos (en tiempo de ejecución) cuando dejemos de necesitarlos. 
 
Para realizar esta administración de la memoria dinámica, C++ cuenta con dos 
operadores new y delete. Antes de utilizarlos, debemos incluir el encabezado <new>. 
https://es.wikipedia.org/wiki/Memoria_(inform%C3%A1tica)
https://es.wikipedia.org/wiki/Tiempo_de_ejecuci%C3%B3n
https://es.wikipedia.org/wiki/Puntero_(inform%C3%A1tica)
https://es.wikipedia.org/wiki/Compilaci%C3%B3n
El operador new reserva memoria dinámica de cualquier tipo, esto es: 
• tipos primitivos (int, double, etc) 
• tipos definidos por el usuario (clases o estructuras). 
 
Con ayuda de los punteros C++ permite reservar dinámicamente espacios de 
memoria ubicados en la zona que se conoce como Heap que comparte los recursos de 
memoria con el Stack. Para la reserva de memoria existen dos operadores, el primero es el 
operador new que se utiliza para reservar posiciones individuales de memoria del tamaño 
del tipo de dato que se va a alojar en esa posición. Mientras que el operador new[] permite 
reservar al tiempo varias posiciones consecutivas de memoria como en el caso de arreglos. 
 
El problema con la reserva dinámica de memoria es que debe ser liberada de nuevo 
de manera manual una vez no se necesita más, ya que en C++ a diferencia de otros 
lenguajes de programación no existe una entidad que se encargue de hacer esta liberación 
de memoria de manera automática (ejemplo: garbage collector), por tanto es necesario el 
uso de otros operadores o funciones que permitan realizar esa liberación de memoria, que 
en caso de no hacerse correctamente da lugar al problema de fuga de memoria o "memory 
leak". Entonces para liberar la memoria previamente reservada existen los operadores 
delete y delete[] que sirven para liberar la memoria reservada con los operadores new y 
new[] respectivamente. 
 
NOTA: Para evitar el problema de fuga de memoria las nuevas versiones de C++ vienen 
con unas clases especiales llamadas Smart Pointers que automatizan el proceso de 
liberación de memoria y además brindan métodos para la reserva de memoria sin necesidad 
de utilizar directamente los operadores new y new[]. 
 
El siguiente código de ejemplo ilustra el procedimiento de reserva y liberación de 
memoria dinámica con los operadores new y delete. 
 
¿Qué es un puntero? 
Es una variable que contiene una posición de memoria, y por lo tanto se dice que 
apunta a esa posición de memoria. 
 
Memoria dinámica en C# 
La mayor parte del código de C# que se escribe es "código seguro comprobable". El 
código seguro comprobable significa que las herramientas de .NET pueden comprobar que 
el código es seguro. En general, el código seguro no accede directamente a la memoria 
mediante punteros. 
 
C# admiteun contexto unsafe, en el que se puede escribir código no comprobable. 
En un contexto unsafe, el código puede usar punteros, asignar y liberar bloques de memoria 
y llamar a métodos mediante punteros de función. El código no seguro en C# no es 
necesariamente peligroso; solo es código cuya seguridad no se puede comprobar. 
Propiedades del código no seguro: 
• El código no seguro es necesario al llamar a funciones nativas que requieren 
punteros. 
• En algunos casos, el código no seguro puede aumentar el rendimiento de la 
aplicación al eliminar las comprobaciones de límites de matriz. 
• El código no seguro presenta riesgos para la seguridad y la estabilidad. 
• El código que contenga bloques no seguros deberá compilarse con la opción 
del compilador AllowUnsafeBlocks. 
En C# se accede a la memoria usando un tipo de dato especial llamado puntero. Un 
puntero es una variable cuyo valor apunta a una dirección especifica de la memoria. En C# 
un puntero se declara con un asterisco situado entre el tipo de puntero y su identificador. 
 
Ejemplo: 
int * MyIntegerPointer 
La expresión anterior declara un puntero llamado “MyIntegerPointer”. El tipo del 
puntero indica el tipo de la variable a la que el puntero puede apuntar. Por ejemplo, un 
puntero entero solo puede apuntar a memoria usada por una variable entera. Los punteros 
deben ser asignados a una dirección de memoria y C# hace que sea fácil escribir una 
expresión que evalúe la dirección de memoria de una variable. Si se antepone el operador 
de concatenación, el símbolo de unión, a una expresión unaria devuelve una dirección de 
memoria. Ejemplo: 
int MyInteger = 123; 
int * MyIntegerPointer = &MyInteger 
Este código hace dos cosas: 
• Declara una variable entera llamada “MyInteger” y le asigna el valor de 
123 
• Declara una variable entera llamada “MyIntegerPointer” y la apunta en la 
dirección de la variable “MyInteger”. 
 
 
Los punteros en realidad tienen dos valores: 
▪ El valor de la dirección de memoria del puntero. 
▪ El valor de la variable a la que apunta el puntero. 
 
C# permite escribir expresiones que evalúen cualquiera de los dos valores. Si se 
antepone un asterisco al identificador del puntero se obtiene el valor de la variable a la que 
apunta el puntero. 
 
 
El código anterior escribe en la consola 123. 
Operadores de gestión de punteros 
 
 
 
 
 
 
 
 
 
 
 
Tipos de puntero 
Los punteros pueden tener uno de los siguientes tipos: 
▪ sbyte 
▪ byte 
▪ short 
▪ ushort 
▪ int 
▪ uint 
▪ long 
▪ ulong 
▪ char 
▪ float 
▪ double 
▪ decimal 
▪ bool 
▪ void. Se usa para especificar un puntero para un tipo desconocido 
 
Como compilar código no seguro 
Por defecto, el compilador de C# sólo compila código seguro de C#. Para obligar al 
compilador a compilar código de C# no seguro debe usar el argumento del compilador 
/unsafe: 
 
El código no seguro permite escribir código que acceda directamente a la memoria, 
sin hacer caso de los objetos que gestionan la memoria en las aplicaciones. 
Como a las direcciones de memoria se accede directamente, el código no seguro puede 
funcionar mejor en algunos tipos de aplicaciones. Esta instrucción compila el archivo 
fuente y permite compilar código no seguro de C#. 
 
Como especificar punteros en modo no seguro 
EL compilador de C# por defecto no permite usar punteros en el código C#. Si intenta trabajar 
con punteros en su código, el compilador C# emitirá el sig. Error: 
 
Los punteros en C# solo son válidos en código no seguro. 
Hay que definir explícitamente el código no seguro al compilador, para hacerlo,se emplea la 
palabra clave unsafe, esta debe aplicarse a un bloque de código que use punteros. 
Para especificar que un bloque de código se ejecute en modo no seguro, se aplica la palabra 
clave unsafe en la declaración del cuerpo del código, por ejemplo: 
 
La palabra unsafe indica que todo el código debe ser considerado no seguro, después de la 
palabra clave, el código del método puede usar constructores de punteros no seguros. 
Ojo: 
La palabra unsafe solo aplica al método en el que aparece, si la clase va a contener otro 
método, este otro método no podrá usar constructores de puntero no seguro a menos qe sea 
declarado con la palabra unsafe. 
Reglas del modificador unsafe: 
 
-Clases, estructuras y delegados pueden incluir el modificador unsafe que indica que todo el 
cuerpo se considera no seguro. 
-Campos, métodos, propiedades, eventos, indizadores, operadores, constructores, 
destructores estáticos pueden definirse con el modificador unsafe indica que la declaración 
del miembro no es segura. 
-Un bloque de código puede ser marcado con el modificador unsafe que indica que todo el 
código sebe ser considerado no seguro. 
 
Como acceder a los valores de los miembros mediante punteros 
 
En C# se permite usar el operador -> para acceder a los miembros de las estructuras 
a las que hace referencia el puntero. 
 
Si se usa el ese operador en el modo seguro, compilador de C# emitirá un mensaje de 
error. 
 
 
¿Cómo comparar punteros? 
 
El modo inseguro de C# permite comparar punteros usando los siguientes operadores: 
• Igualdad (==) 
• Desigualdad (!=) 
• Menor que (<) y Mayor que (>) 
• Menor o igual que (<=) y Mayor o igual que (>=) 
 
Estos operadores devuelven los valores booleanos “true” o “false” cuando se usan con tipos 
de punteros. 
 
Cálculo con punteros 
 
Es posible combinar punteros con valores enteros en expresiones matemáticas para 
cambiar la posición a la que apunta el puntero. El operador “+” suma un valor al puntero, 
mientras que el operador “-” resta un valor del puntero. La instrucción “fixed” también puede 
escribirse como se indica a continuación: 
 
En este bloque de código, el puntero es desplazado por un valor y la suma se usa para 
apuntar a una dirección de memoria. La siguiente expresión realiza aritmética de puntero: 
 
Esta instrucción se interpreta como: “Toma el valor de “IntergerPointer” e 
increméntalo en el número de posiciones especificadas por “ArrayIndex”. Coloca el valor de 
“ArrayIndex” en esa posición. 
 
La aritmética de puntero aumenta la posición de un puntero en un numero 
especificado de bytes, dependiendo del tamaño del tipo al que se está apuntando. 
 
¿Como usar el operador sizeof? 
 
Se puede usar el operador sizeof en modo no seguro para calcular el número d ebytes 
necesarios para contener un tipo de datos específico. El operador va seguido por un nombre 
de tipo no administrado entre paréntesis y la expresión da como resultado un número entero 
que especifica el número de bytes necesario para contener una variable del tipo 
especificado. 
 
Esta tabla enumera los tipos administrados admitidos y los valores que devuelve una 
operación sizeof. 
Tipos sizeof() admitidos 
Expresión Resultado 
sizeof(sbyte) 1 
sizeof(byte) 1 
sizeof(short) 2 
sizeof(ushort) 2 
sizeof(int) 4 
sizeof(uint) 4 
sizeof(long) 8 
sizeof(ulong) 8 
sizeof(char) 2 
sizeof(float) 4 
sizeof(double) 8 
sizeof(bool) 1 
 
 
¿Cómo asignar espacio de la pila para la memoria? 
 
C# proporciona un sencillo mecanismo de asignación de memoria en código no seguro. 
Puede solicitar memoria en modo no seguro usando la palabra clave de C# stackalloc, de la 
siguiente manera: 
 
 
Tras la palabra clave stackalloc se escribe un tipo de dato. Devuelve un puntero al 
bloque de memoria al que se le asigna el espacio y se puede usar la memoria exactamente 
igual que la memoria gestionada por el CLR. 
 
No hay una operación explicita para liberar la memoria asignada por la palabra clave 
stackalloc. La memoria se libera automáticamente cando finaliza el método que signó esa 
memoria. 
 
Resumen 
 
El modo no seguro de C# permite a su código trabajardirectamente con la memoria. 
Su uso puede mejorar el rendimiento porque el código accede directamente a la memoria, 
sin tener que moverse con cuidado por el CLR. Sin embargo, el modo no seguro puede ser 
peligroso y puede hacer que el código falle si no trabaja adecuadamente con la memoria. 
 
En general, evite el uso del modo no seguro de C#. Si necesita un poco más de 
rendimiento para su código o si está trabajando con código heredado de C o C++ que 
necesita que especifique una posición de memoria, siga con el modo seguro que se ofrece 
por defecto y deje que el CLR gestione lo detalles de la asignación de memoria. 
1.5 Análisis de algoritmos 
 
En el análisis teórico de algoritmos, es común estimar su complejidad en el sentido 
asintótico, es decir, estimar la función de complejidad para entradas arbitrariamente 
grandes. El término «análisis de algoritmos» fue acuñado por Donald Knuth. 
El análisis de algoritmos es una parte importante de la teoría de la complejidad 
computacional, que proporciona una estimación teórica de los recursos necesarios de un 
algoritmo para resolver un problema computacional específico. La mayoría de los algoritmos 
están diseñados para trabajar con entradas de longitud arbitraria. El análisis de algoritmos es 
la determinación de la cantidad de recursos de tiempo y espacio necesarios para ejecutarlo. 
Por lo general, la eficiencia o el tiempo de ejecución de un algoritmo se establece 
como una función que relaciona la longitud de entrada con el número de pasos, conocido 
como complejidad de tiempo o volumen de memoria, conocido como complejidad de 
espacio. 
Complejidad Algorítmica. 
¿De qué hablamos cuando hablamos de complejidad? 
Resulta evidente que el tiempo real requerido por una computadora para la ejecución de 
algoritmo es directamente proporcional al número de operaciones básicas que la 
computadora debe realizar en su ejecución. Medir por lo tanto el tiempo real de ejecución 
equivale a medir el número de operaciones elementales realizadas. Desde ahora supondremos 
que todas las operaciones básicas se ejecutan en una unidad de tiempo. Por esta razón se suele 
llamar tiempo de ejecución no al tiempo real físico, sino al número de operaciones 
elementales realizadas. 
Otro de los factores importantes, en ocasiones decisivo, para comparar algoritmos es la 
cantidad de memoria del computador requerida para almacenar los datos durante el proceso. 
 
https://es.wikipedia.org/wiki/Donald_Knuth
Al no ser única la manera de representar un algoritmo mediante un programa, y al no ser 
único el computador en el cual se ejecutará, resulta que la medida del tiempo será variable 
dependiendo fundamentalmente de los siguientes factores: 
• 1) El lenguaje de programación elegido 
• 2) El programa que representa 
• 3) El computador que lo ejecuta 
Por eso surge la necesidad de medir el tiempo requerido por un algoritmo 
independientemente de su representación y del computador que lo ejecute. 
El análisis de algoritmos se encarga del estudio del tiempo y espacio requerido por 
un algoritmo para su ejecución. Ambos parámetros pueden ser estudiados con respecto al 
peor caso (también conocido como caso general) o respecto al caso probabilístico (o caso 
esperado). 
En Ciencias de la Computación, el término eficiencia algorítmica es usado para 
describir aquellas propiedades de los algoritmos que están relacionadas con la cantidad de 
recursos utilizados por el algoritmo. Un algoritmo debe ser analizado para determinar el uso 
de los recursos que realiza. La eficiencia algorítmica puede ser vista como análogo a la 
ingeniería de productividad de un proceso repetitivo o continuo. 
 
Con el objetivo de lograr una eficiencia máxima se quiere minimizar el uso de 
recursos. Sin embargo, varias medidas (complejidad temporal, complejidad espacial) no 
pueden ser comparadas directamente, luego, cual de dos algoritmos es considerado más 
eficiente, depende de cual medida de eficiencia se está considerando como prioridad; por 
ejemplo, la prioridad podría ser obtener la salida del algoritmo lo más rápido posible, o que 
minimice el uso de la memoria, o alguna otra medida particular. 
 
 
Una diferencia significativa entre el análisis de complejidad de algoritmos y la teoría 
de la complejidad computacional, es que el primero se dedica a determinar la cantidad de 
recursos requeridos por un algoritmo en particular para resolver un problema, mientras que 
la segunda, analiza todos los posibles algoritmos que pudieran ser usados para resolver el 
mismo problema. 
 
La importancia de la eficiencia con respecto a la complejidad temporal fue enfatizada 
por Ada Lovelace en 1843 como resultado de su trabajo con el motor analítico mecánico 
de Charles Babbage: «En casi todo cómputo son posibles una gran variedad de 
configuraciones para la sucesión de un proceso, y varias consideraciones pueden influir en 
la selección de estas según el propósito de un motor de cálculos. Una objetivo esencial es 
escoger la configuración que tienda a minimizar el tiempo necesario para completar el 
cálculo.» 
Existen muchas maneras para medir la cantidad de recursos utilizados por un 
algoritmo: las dos medidas más comunes son la complejidad temporal y espacial; otras 
medidas a tener en cuenta podrían ser la velocidad de transmisión, uso temporal del disco 
duro, así como uso del mismo a largo plazo, consumo de energía, tiempo de respuesta ante 
los cambios externos, etc. Muchas de estas medidas dependen del tamaño de la entrada del 
algoritmo ( Ej. la cantidad de datos a ser procesados); además podrían depender de la forma 
en que los datos están organizados (Ej. algoritmos de ordenación necesitan hacer muy poco 
en datos que ya están ordenados o que están ordenados de forma inversa). 
 
En la práctica existen otros factores que pueden afectar la eficiencia de un algoritmo, 
tales como la necesidad de cierta precisión y/o veracidad. La forma en que un algoritmo es 
implementado también puede tener un efecto de peso en su eficiencia, muchos de los aspectos 
asociados a la implementación se vinculan a problemas de optimización. 
 
 
https://es.wikipedia.org/wiki/Ada_Lovelace
https://es.wikipedia.org/wiki/Charles_Babbage
Necesidad de análisis 
La necesidad de analizar algoritmos surge como necesidad de eficiencia, es decir elegir 
un mejor algoritmo para un problema particular, ya que un problema computacional puede 
resolverse mediante diferentes algoritmos. 
Al considerar un algoritmo para un problema específico, podemos comenzar a desarrollar 
el reconocimiento de patrones de modo que la ayuda de este algoritmo pueda resolver tipos 
similares de problemas. 
Los algoritmos a menudo son bastante diferentes entre sí, aunque el objetivo de estos 
algoritmos es el mismo. Por ejemplo, sabemos que un conjunto de números se puede ordenar 
usando diferentes algoritmos. El número de comparaciones realizadas por un algoritmo 
puede variar con otros para la misma entrada. Por lo tanto, la complejidad temporal de esos 
algoritmos puede diferir. Al mismo tiempo, necesitamos calcular el espacio de memoria 
requerido por cada algoritmo. 
El análisis del algoritmo es el proceso de analizar la capacidad de resolución de 
problemas del algoritmo en términos del tiempo y el tamaño requeridos (el tamaño de la 
memoria para el almacenamiento durante la implementación). Sin embargo, la principal 
preocupación del análisis de algoritmos es el tiempo o rendimiento requerido. En general, 
realizamos los siguientes tipos de análisis: 
• El peor de los casos: el número máximo de pasos dados en cualquier instancia de 
tamaño N. 
• El mejor caso : el número mínimo de pasos dados en cualquier instancia de tamaño 
N. 
• El caso promedio : un número promedio de pasos dados en cualquier instancia de 
tamaño N. 
• El amortizado : una secuencia de operaciones aplicadas a la entrada de tamaño 
promediada en eltiempo. 
Para resolver un problema, debemos tener en cuenta el tiempo y la complejidad del 
espacio, ya que el programa puede ejecutarse en un sistema donde la memoria es limitada, 
pero hay suficiente espacio disponible o viceversa. En este contexto, si comparamos el 
ordenamiento de burbuja y el de fusión. El ordenamiento de burbuja no requiere memoria 
adicional, pero el ordenamiento por fusión requiere espacio adicional. Aunque la 
complejidad temporal del ordenamiento de burbuja es mayor en comparación con el 
ordenamiento de fusión, es posible que necesitemos aplicar el ordenamiento de burbuja si el 
programa necesita ejecutarse en un entorno, donde la memoria es muy limitada.