Estructuras de datos y algoritmos: descripción general
La estructura de datos es una forma sistemática de organizar los datos para usarlos de manera eficiente. Los siguientes términos son los términos fundamentales de una estructura de datos.
Interface- Cada estructura de datos tiene una interfaz. La interfaz representa el conjunto de operaciones que admite una estructura de datos. Una interfaz solo proporciona la lista de operaciones admitidas, el tipo de parámetros que pueden aceptar y el tipo de retorno de estas operaciones.
Implementation- La implementación proporciona la representación interna de una estructura de datos. La implementación también proporciona la definición de los algoritmos utilizados en las operaciones de la estructura de datos.
Características de una estructura de datos
Correctness - La implementación de la estructura de datos debe implementar su interfaz correctamente.
Time Complexity - El tiempo de ejecución o el tiempo de ejecución de operaciones de estructura de datos debe ser lo más pequeño posible.
Space Complexity - El uso de memoria de una operación de estructura de datos debe ser lo mínimo posible.
Necesidad de estructura de datos
A medida que las aplicaciones se vuelven complejas y ricas en datos, existen tres problemas comunes a los que se enfrentan las aplicaciones hoy en día.
Data Search- Considere un inventario de 1 millón (10 6 ) artículos de una tienda. Si la aplicación va a buscar un elemento, tiene que buscar un elemento en 1 millón (10 6 ) elementos cada vez que ralentiza la búsqueda. A medida que aumentan los datos, la búsqueda se volverá más lenta.
Processor speed - La velocidad del procesador, aunque es muy alta, se ve limitada si los datos aumentan a mil millones de registros.
Multiple requests - Dado que miles de usuarios pueden buscar datos simultáneamente en un servidor web, incluso el servidor rápido falla al buscar los datos.
Para solucionar los problemas antes mencionados, las estructuras de datos vienen al rescate. Los datos se pueden organizar en una estructura de datos de tal manera que no sea necesario buscar en todos los elementos, y los datos requeridos se pueden buscar casi instantáneamente.
Casos de tiempo de ejecución
Hay tres casos que se utilizan normalmente para comparar el tiempo de ejecución de varias estructuras de datos de forma relativa.
Worst Case- Este es el escenario donde una operación de estructura de datos particular toma el máximo tiempo que puede tomar. Si el tiempo del peor caso de una operación es ƒ (n), entonces esta operación no tomará más de ƒ (n) tiempo donde ƒ (n) representa la función de n.
Average Case- Este es el escenario que representa el tiempo medio de ejecución de una operación de una estructura de datos. Si una operación toma ƒ (n) tiempo en ejecución, entonces m operaciones tomarán mƒ (n) tiempo.
Best Case- Este es el escenario que representa el menor tiempo de ejecución posible de una operación de una estructura de datos. Si una operación toma ƒ (n) tiempo en ejecución, entonces la operación real puede tomar tiempo como el número aleatorio que sería máximo como ƒ (n).
Terminología básica
Data - Los datos son valores o conjunto de valores.
Data Item - El elemento de datos se refiere a una sola unidad de valores.
Group Items - Los elementos de datos que se dividen en subelementos se denominan Elementos de grupo.
Elementary Items - Los elementos de datos que no se pueden dividir se denominan elementos elementales.
Attribute and Entity - Una entidad es aquella que contiene ciertos atributos o propiedades, a las que se les pueden asignar valores.
Entity Set - Las entidades de atributos similares forman un conjunto de entidades.
Field - El campo es una sola unidad elemental de información que representa un atributo de una entidad.
Record - Registro es una colección de valores de campo de una entidad determinada.
File - El archivo es una colección de registros de las entidades en un conjunto de entidades dado.