La estructura de datos es una forma de definir, almacenar y recuperar datos de forma estructural y sistemática. Una estructura de datos puede contener diferentes tipos de elementos de datos.
La disponibilidad de la estructura de datos puede variar según los lenguajes de programación. Las estructuras de datos comúnmente disponibles son lista, matrices, pila, colas, gráfico, árbol, etc.
El algoritmo es un procedimiento paso a paso, que define un conjunto de instrucciones que se ejecutarán en cierto orden para obtener la salida deseada.
Un problema se puede resolver de más de una forma. Entonces, se pueden derivar muchos algoritmos de solución para un problema dado. Analizamos los algoritmos disponibles para encontrar e implementar el algoritmo más adecuado.
Un algoritmo generalmente se analiza en dos factores: tiempo y espacio. Es decir, cuantoexecution tiempo y cuanto extra space requerido por el algoritmo.
El análisis asintótico de un algoritmo se refiere a la definición de la base / estructura matemática de su rendimiento en tiempo de ejecución. Usando el análisis asintótico, podemos concluir muy bien el mejor de los casos, el caso promedio y el peor de los casos de un algoritmo.
El análisis asintótico puede proporcionar tres niveles de enlace matemático del tiempo de ejecución de un algoritmo:
- El mejor caso está representado por la notación Ω (n).
- El peor de los casos está representado por la notación Ο (n).
- El caso promedio está representado por la notación Θ (n).
Una estructura de datos lineal tiene elementos de datos ordenados secuencialmente. La próxima vez se puede ubicar en la siguiente dirección de memoria. Se almacena y se accede a él de forma secuencial. Array y list son ejemplos de estructura de datos lineal.
Las siguientes operaciones se realizan comúnmente en cualquier estructura de datos:
Insertion - agregar un elemento de datos
Deletion - eliminar un elemento de datos
Traversal - acceder y / o imprimir todos los elementos de datos
Searching - encontrar un elemento de datos en particular
Sorting - organizar elementos de datos en una secuencia predefinida
Hay tres enfoques de uso común para desarrollar algoritmos:
Greedy Approach - encontrar una solución eligiendo la siguiente mejor opción
Divide and Conquer - sumergir el problema en un subproblema mínimo posible y resolverlos de forma independiente
Dynamic Programming - sumergir el problema en un subproblema mínimo posible y resolverlos de forma combinada
Los problemas dados a continuación encuentran su solución utilizando un enfoque de algoritmo codicioso:
- Problema del vendedor ambulante
- Algoritmo de árbol de expansión mínimo de Prim
- Algoritmo de árbol de expansión mínimo de Kruskal
- Algoritmo de árbol de expansión mínimo de Dijkstra
- Gráfico - Colorear Mapa
- Gráfico - Cubierta de vértice
- Problema de la mochila
- Problema de programación de trabajos
Los problemas dados a continuación encuentran su solución utilizando el enfoque del algoritmo de dividir y conquistar:
- Combinar ordenar
- Ordenación rápida
- Búsqueda binaria
- Multiplicación de matrices de Strassen
- Par más cercano (puntos)
Los problemas dados a continuación encuentran su solución utilizando el enfoque del algoritmo de dividir y conquistar:
- Serie de números de Fibonacci
- Problema de la mochila
- Torre de Hanoi
- Todos emparejan el camino más corto de Floyd-Warshall
- El camino más corto por Dijkstra
- Programación de proyectos
Una lista vinculada es una lista de elementos de datos conectados con vínculos, es decir, punteros o referencias. La mayoría de los lenguajes de programación de alto nivel modernos no proporcionan la función de acceder directamente a la ubicación de la memoria, por lo tanto, las listas vinculadas no son compatibles con ellos ni están disponibles en forma de funciones incorporadas.
En la estructura de datos, la pila es un tipo de datos abstracto (ADT) que se utiliza para almacenar y recuperar valores en el método Último en entrar, primero en salir.
Las pilas siguen el método LIFO y la adición y recuperación de un elemento de datos toma solo Ο (n) tiempo. Las pilas se utilizan cuando necesitamos acceder a los datos en orden inverso o en su llegada. Las pilas se usan comúnmente en llamadas de funciones recursivas, análisis de expresiones, primer recorrido en profundidad de gráficos, etc.
Las siguientes operaciones se pueden realizar en una pila:
push() - agrega un artículo para apilar
pop() - elimina el elemento de la pila superior
peek() - da valor al artículo superior sin quitarlo
isempty() - comprueba si la pila está vacía
isfull() - comprueba si la pila está llena
La cola es una estructura de datos abstracta, algo similar a la pila. A diferencia de la pila, la cola se abre en ambos extremos. Un extremo siempre se usa para insertar datos (poner en cola) y el otro se usa para eliminar datos (quitar de cola). La cola sigue la metodología First-In-First-Out, es decir, se accederá primero al elemento de datos almacenado primero.
Como las colas siguen el método FIFO, se utilizan cuando necesitamos trabajar en elementos de datos en la secuencia exacta de su llegada. Cada sistema operativo mantiene colas de varios procesos. Las colas de prioridad y la amplitud del primer recorrido de los gráficos son algunos ejemplos de colas.
Las siguientes operaciones se pueden realizar en una pila:
enqueue() - agrega un elemento al final de la cola
dequeue() - elimina el artículo del frente de la cola
peek() - da valor al artículo frontal sin quitarlo
isempty() - comprueba si la pila está vacía
isfull() - comprueba si la pila está llena
La búsqueda lineal intenta encontrar un elemento en un tipo de datos organizado secuencialmente. Estos elementos de datos ordenados secuencialmente, conocidos como matriz o lista, son accesibles en una ubicación de memoria creciente. La búsqueda lineal compara el elemento de datos esperado con cada uno de los elementos de datos en la lista o matriz. La complejidad de tiempo promedio del caso de la búsqueda lineal es Ο (n) y la complejidad del caso más desfavorable es Ο (n 2 ). No es necesario ordenar los datos de las matrices / listas de destino.
Una búsqueda binaria solo funciona en listas o matrices ordenadas. Esta búsqueda selecciona el medio que divide la lista completa en dos partes. Primero se compara el medio.
Esta búsqueda primero compara el valor objetivo con la mitad de la lista. Si no se encuentra, toma una decisión sobre si.
La clasificación de burbujas es un algoritmo basado en comparación en el que se compara cada par de elementos adyacentes y los elementos se intercambian si no están en orden. Debido a que la complejidad del tiempo es Ο (n 2 ), no es adecuado para un gran conjunto de datos.
La clasificación por inserción divide la lista en dos sublistas, ordenadas y sin clasificar. Toma un elemento a la vez y lo encuentra en la ubicación adecuada en la sublista ordenada e inserta allí. La salida después de la inserción es una sublista ordenada. Funciona de forma iterativa en todos los elementos de la sublista sin clasificar y los inserta en la sublista ordenada en orden.
La clasificación por selección es una técnica de clasificación en el lugar. Divide el conjunto de datos en dos sublistas: ordenadas y no ordenadas. Luego, selecciona el elemento mínimo de la sublista sin clasificar y lo coloca en la lista ordenada. Esto se repite a menos que todos los elementos de la sublista sin clasificar se consuman en una sublista ordenada.
Ambas técnicas de clasificación mantienen dos sublistas, clasificadas y sin clasificar, y ambas toman un elemento a la vez y lo colocan en una sublista ordenada. La ordenación por inserción funciona en el elemento actual disponible y lo coloca en la matriz ordenada en la ubicación apropiada manteniendo las propiedades de la ordenación por inserción. Considerando que, la ordenación por selección busca el mínimo de la sublista sin clasificar y lo reemplaza con el elemento actual en la mano.
Merge sort es un algoritmo de clasificación basado en el enfoque de programación divide y vencerás. Sigue dividiendo la lista en sublistas más pequeñas hasta que todas las sublistas tienen solo 1 elemento. Y luego los fusiona de forma ordenada hasta que se consumen todas las sublistas. Tiene una complejidad en tiempo de ejecución de Ο (n log n) y necesita Ο (n) espacio auxiliar.
Se puede decir que el tipo de shell es una variante del tipo de inserción. La ordenación de shell divide la lista en sublistas más pequeñas en función de algunosgapvariable y luego cada sublista se ordena mediante ordenación por inserción. En el mejor de los casos, puede funcionar hasta Ο (n log n).
La clasificación rápida utiliza el enfoque de dividir y conquistar. Divide la lista en 'particiones' más pequeñas usando 'pivote'. Los valores que son más pequeños que el pivote se organizan en la partición izquierda y los valores mayores se organizan en la partición derecha. Cada partición se ordena de forma recursiva mediante ordenación rápida.
Un gráfico es una representación pictórica de un conjunto de objetos donde algunos pares de objetos están conectados por enlaces. Los objetos interconectados se representan mediante puntos denominados vértices y los vínculos que conectan los vértices se denominan aristas.
El algoritmo Depth First Search (DFS) atraviesa un gráfico en un movimiento de profundidad y usa una pila para recordar obtener el siguiente vértice para iniciar una búsqueda cuando se produce un callejón sin salida en cualquier iteración.
El algoritmo Breadth First Search (BFS) atraviesa un gráfico en un movimiento amplio y utiliza una cola para recordar obtener el siguiente vértice para iniciar una búsqueda cuando se produce un callejón sin salida en cualquier iteración.
Un árbol es un gráfico mínimamente conectado que no tiene bucles ni circuitos.
Un árbol binario tiene la condición especial de que cada nodo puede tener dos hijos como máximo.
Un árbol de búsqueda binario es un árbol binario con una disposición especial donde el hijo izquierdo de un nodo debe tener un valor menor que el valor de su padre y el hijo derecho del nodo debe tener un valor mayor que su valor padre.
El recorrido del árbol es un proceso para visitar todos los nodos de un árbol. Porque todos los nodos están conectados a través de bordes (enlaces), siempre comenzamos desde el nodo raíz (cabeza). Hay tres formas que usamos para atravesar un árbol:
- Recorrido en orden
- Traversal de reserva
- Recorrido posterior al pedido
- Recorrido en orden - 10 14 19 27 31 35 42
- Recorrido de reserva - 27 14 10 19 35 31 42
- Recorrido posterior al pedido - 10 19 14 31 42 35 27
Los árboles AVL son árboles de búsqueda binaria de equilibrio de altura. El árbol AVL verifica la altura de los subárboles izquierdo y derecho y asegura que la diferencia no sea mayor a 1. Esta diferencia se llama Factor de equilibrio.
BalanceFactor = height(left-sutree) − height(right-sutree)Un árbol de expansión es un subconjunto del Gráfico G, que tiene todos los vértices cubiertos con el mínimo número posible de aristas. Un árbol de expansión no tiene ciclos y no se puede desconectar.
Depende de qué tan conectado esté el gráfico. Un gráfico completo no dirigido puede tener un número máximo de árboles de expansión n n-1 , donde n es el número de nodos.
Este algoritmo trata el gráfico como un bosque y cada nodo como un árbol individual. Un árbol se conecta a otro solo y solo si tiene el menor costo entre todas las opciones disponibles y no viola las propiedades de MST.
El algoritmo de Prim trata los nodos como un solo árbol y sigue agregando nuevos nodos al árbol de expansión desde el gráfico dado.
En un gráfico ponderado, un árbol de expansión mínimo es un árbol de expansión que tiene un peso mínimo que todos los demás árboles de expansión del mismo gráfico.
Heap es una estructura de datos de árbol binario equilibrado especial donde la clave del nodo raíz se compara con sus hijos y se organiza en consecuencia. Un min-heap, un nodo padre tiene un valor clave menor que sus hijos y un nodo padre max-heap tiene un valor mayor que sus hijos.
Una función recursiva es aquella que se llama a sí misma, directamente o llama a una función que a su vez la llama. Cada función recursiva sigue las propiedades recursivas:base criteria donde las funciones dejan de llamarse a sí mismas y progressive approach donde las funciones intentan cumplir los criterios básicos en cada iteración.
Tower of Hanoi, es un rompecabezas matemático que consta de tres torres (clavijas) y más de un anillo. Todos los anillos son de diferente tamaño y se apilan unos sobre otros donde el disco grande siempre está debajo del disco pequeño. El objetivo es mover la torre de disco de una clavija a otra, sin romper sus propiedades.
La serie Fibonacci genera un número subsiguiente agregando dos números anteriores. Por ejemplo, 0 1 1 2 3 5 8 13.
El hash es una técnica para convertir un rango de valores clave en un rango de índices de una matriz. Mediante el uso de tablas hash, podemos crear un almacenamiento de datos asociativo donde se puede encontrar el índice de datos proporcionando sus valores clave.
La búsqueda por interpolación es una variante mejorada de la búsqueda binaria. Este algoritmo de búsqueda trabaja en la posición de prueba del valor requerido.
Notación de prefijo - * + ab + cd
Notación de sufijo - ab + cd + *