Leela Krishna
Leela Krishna

Seguir

1 de abril de 2019 · 4 min read

en el lenguaje de programación swift…

Parte -1:

¿por Qué las Estructuras de Datos?

Al crear aplicaciones modernas, a menudo se pasa por alto gran parte de la teoría inherente a los algoritmos. Para las soluciones que consumen cantidades relativamente pequeñas de datos, las decisiones sobre técnicas o patrones de diseño específicos pueden no ser tan importantes como hacer que las cosas funcionen. Sin embargo, a medida que la audiencia crece, también lo harán los datos. Gran parte de lo que las grandes empresas de tecnología tienen éxito es su capacidad para interpretar grandes cantidades de datos. Dar sentido a los datos permite a los usuarios conectarse, compartir, completar transacciones y tomar decisiones.

→ Estructuras de datos :

  • Estructuras de datos fundamentales(Elementales)

Pila, Cola, Algoritmos de clasificación

  • Árboles

Árboles & Árboles Binarios, Búsqueda Binaria, Montón, Clasificación en Montón, Cola de prioridad

  • Gráficos

, Lista de Adyacencia, Algoritmo de Dijkstra, Algoritmo de Prim

→ Notación O Grande :

El análisis asintótico es el proceso de describir la eficiencia de los algoritmos, y se expresa comúnmente en un formato común conocido como Notación O grande.

  • Complejidad temporal :

La cantidad de tiempo para completar el algoritmo (función) a medida que crece su tamaño de entrada(n).

  • Complejidad espacial :

La cantidad de memoria (espacio) necesaria para que se ejecute un algoritmo(función).

Ambos pueden expresarse en notación O Grande.

  • Complejidades de Tiempo Más Comunes:

→ Tiempo Constante (O(1)) :-

Un algoritmo de tiempo constante es el que tiene el mismo tiempo de ejecución independientemente de su entrada. La notación O Grande para esto es O (1).

→ Tiempo Lineal (O(n)) :-

Un algoritmo de tiempo lineal es que su velocidad depende de su tamaño de entrada. En otras palabras, se vuelve menos eficiente a medida que crece su tamaño de entrada(n).

→ Tiempo cuadrático (O (n2)) :-

se refiere a un algoritmo que lleva tiempo al tamaño proporcional al cuadrado del tamaño de entrada. Rápidamente se sale de control a medida que aumenta el tamaño de entrada.

→ Tiempo logarítmico (O (log n)) :-

Un algoritmo común con complejidad de tiempo O (log n) es la búsqueda binaria cuya relación recursiva es T(n/2) + O(1), es decir, en cada nivel posterior del árbol se divide el problema por la mitad y se realiza una cantidad constante de trabajo adicional.

→ Tiempo cuasilineal (O (n log n)) :-

Se dice que un algoritmo se ejecuta en tiempo cuasilineal (también conocido como tiempo log-lineal) si T(n) = O(n log^k n) para alguna constante positiva k; el tiempo linearítmico es el caso k = 1.

Ejemplo :

La estructura de datos es una forma sistemática de organizar los datos para utilizarlos de manera eficiente. Los siguientes términos son los términos básicos de una estructura de datos.Interfaz

  • – Cada estructura de datos tiene una interfaz. La interfaz representa el conjunto de operaciones que soporta 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.
  • Implementación: 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:

  • Corrección: La implementación de la estructura de datos debe implementar su interfaz correctamente.
  • Complejidad de tiempo: El tiempo de ejecución o el tiempo de ejecución de las operaciones de la estructura de datos debe ser lo más pequeño posible.
  • Complejidad de espacio: El uso de memoria de una operación de estructura de datos debe ser lo menos posible.

→ Necesidad de estructura de datos:

A medida que las aplicaciones se vuelven complejas y ricas en datos, hay tres problemas comunes a los que se enfrentan las aplicaciones en la actualidad.

  1. Búsqueda de datos: Considere un inventario de 1 millón(106) artículos de una tienda. Si la aplicación va a buscar un elemento, tiene que buscar un elemento en 1 millón (106) elementos cada vez que ralentiza la búsqueda. A medida que los datos crecen, la búsqueda se volverá más lenta.
  2. Velocidad del procesador: la velocidad del procesador, aunque es muy alta, cae limitada si los datos crecen a mil millones de registros.
  3. Múltiples solicitudes: como miles de usuarios pueden buscar datos simultáneamente en un servidor web, incluso el servidor rápido falla al buscar los datos.

Para resolver los problemas mencionados anteriormente, las estructuras de datos vienen a rescatar. 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.

→ Veamos un contenedor de pila en swift:

Creamos un contenedor alrededor de la matriz de swift, donde usamos la matriz como estructura de almacenamiento. Las matrices dan inserciones y eliminaciones de tiempo constante (O(1)) cuando se realizan desde el final de la matriz.

Son Datos FIFO → Primero En Entrar, Primero En Salir.

Ejemplos en iOS : Pila de Uinavigaciones, funcionalidades de Deshacer, etc.

Deja una respuesta

Tu dirección de correo electrónico no será publicada.