DataStructure And Algo
1.0.0
Las estructuras de datos son un medio especializado para organizar y almacenar datos en las computadoras de tal manera que podemos realizar operaciones en los datos almacenados de manera más eficiente. Las estructuras de datos tienen un amplio y diverso alcance de uso en los campos de la informática e ingeniería de software. Las estructuras de datos se están utilizando en casi todos los programas o sistemas de software que se han desarrollado. Además, las estructuras de datos se encuentran bajo los fundamentos de la informática e ingeniería de software. Es un tema clave cuando se trata de preguntas de entrevistas de ingeniería de software. Por lo tanto, como desarrolladores, debemos tener un buen conocimiento sobre las estructuras de datos.
Una matriz es una estructura de tamaño fijo, que puede contener elementos del mismo tipo de datos. Puede ser una variedad de enteros, una variedad de números de punto flotante, una variedad de cadenas o incluso una matriz de matrices (como matrices bidimensionales). Las matrices están indexadas, lo que significa que el acceso aleatorio es posible.
Insertar elementos en una matriz y eliminar elementos de una matriz no se puede hacer de inmediato, ya que las matrices son de tamaño fijo. Si desea insertar un elemento en una matriz, primero deberá crear una nueva matriz con un tamaño aumentado (tamaño actual + 1), copiar los elementos existentes y agregar el nuevo elemento. Lo mismo ocurre con la eliminación con una nueva variedad de tamaño reducido.
Una lista vinculada es una estructura secuencial que consiste en una secuencia de elementos en orden lineal que están vinculados entre sí. Por lo tanto, debe acceder a los datos secuencialmente y el acceso aleatorio no es posible. Las listas vinculadas proporcionan una representación simple y flexible de conjuntos dinámicos.
Una pila es una estructura LIFO (último en primer lugar: al fin se puede acceder al elemento al fin al principio) que se puede encontrar comúnmente en muchos lenguajes de programación. Esta estructura se nombra como "pila" porque se asemeja a una pila del mundo real, una pila de placas.
Utilizado para la evaluación de la expresión (por ejemplo: un algoritmo de yardas de derivación para análisis y evaluación de expresiones matemáticas). Se utiliza para implementar llamadas de funciones en la programación de recursión.
Una cola es una estructura FIFO (primero en primera vez, al principio colocada al principio al principio) que se puede encontrar comúnmente en muchos lenguajes de programación. Esta estructura se nombra como "cola" porque se asemeja a una cola del mundo real, personas que esperan en una cola.
Se usa para administrar hilos en múltiples lectura. Utilizado para implementar sistemas de colas (por ejemplo: colas prioritarias).
Una tabla hash es una estructura de datos que almacena valores que tienen claves asociadas con cada una de ellas. Además, admite la búsqueda de manera eficiente si conocemos la clave asociada con el valor. Por lo tanto, es muy eficiente para insertar y buscar, independientemente del tamaño de los datos.
El direccionamiento directo utiliza la asignación uno a uno entre los valores y las claves al almacenar en una tabla. Sin embargo, hay un problema con este enfoque cuando hay una gran cantidad de pares de valores clave. La tabla será enorme con tantos registros y puede ser poco práctico o incluso imposible de almacenar, dada la memoria disponible en una computadora típica. Para evitar este problema, usamos tablas hash .
Se utiliza una función especial llamada función hash (h) para superar el problema mencionado anteriormente en el direccionamiento directo. En el acceso directo, un valor con la clave K se almacena en la ranura K. Usando la función hash, calculamos el índice de la tabla (ranura) al que va cada valor. El valor calculado utilizando la función hash para una clave dada se denomina valor hash que indica el índice de la tabla a la que se asigna el valor.
Un árbol es una estructura jerárquica donde los datos se organizan jerárquicamente y se unen. Esta estructura es diferente de una lista vinculada, mientras que, en una lista vinculada, los elementos están vinculados en un orden lineal. Se han desarrollado varios tipos de árboles durante las últimas décadas, para adaptarse a ciertas aplicaciones y cumplir con ciertas limitaciones. Algunos ejemplos son el árbol de búsqueda binaria, el árbol B, la árbol, el árbol rojo-negro, el árbol de mantequilla, el árbol AVL y el árbol N-ARY.
Un árbol de búsqueda binario (BST), como su nombre indica, es un árbol binario donde los datos se organizan en una estructura jerárquica. Esta estructura de datos almacena valores en orden ordenado. Cada nodo en un árbol de búsqueda binario comprende los siguientes atributos.
Un árbol de búsqueda binario exhibe una propiedad única que lo distingue de otros árboles. Esta propiedad se conoce como la propiedad ** Binary-Search-Tree **.
Un montón es un caso especial de un árbol binario donde los nodos principales se comparan con sus hijos con sus valores y se organizan en consecuencia.
Los montones pueden ser de 2 tipos.
Un gráfico consiste en un conjunto finito de vértices o nodos y un conjunto de bordes que conectan estos vértices.
El orden de un gráfico es el número de vértices en el gráfico. El tamaño de un gráfico es el número de bordes en el gráfico.
Se dice que dos nodos son adyacentes si están conectados entre sí por el mismo borde.
Se dice que un gráfico G es un gráfico dirigido si todos sus bordes tienen una dirección que indica cuál es el vértice de inicio y cuál es el vértice final . Decimos que (u, v) es un incidente de u deja el vértice u y es incidente o ingresa al vértice v.
Se dice que un gráfico G es un gráfico no dirigido si todos sus bordes no tienen dirección. Puede ir en ambos sentidos entre los dos vértices.
Si un vértice no está conectado a ningún otro nodo en el gráfico, se dice que está aislado .
Un Trie es una estructura de datos de recuperación de información similar a un árbol cuyos nodos almacenan las letras de un alfabeto. También se conoce como un árbol digital o un árbol Radix o un árbol de prefijo.
Trie es una estructura de datos de recuperación de información eficiente. Usando TRIE, las complejidades de búsqueda se pueden llevar al límite óptimo (longitud de llave). Si almacenamos claves en el árbol de búsqueda binario, un BST bien equilibrado necesitará tiempo proporcional a M * log n, donde M es la longitud máxima de la cadena y N es el número de teclas en el árbol. Usando Trie, podemos buscar la clave en el tiempo o (m) .
1. Trie estándar : es un árbol ordenado como la estructura de datos.
2. Trie comprimido : se utiliza para lograr la optimización del espacio. Un trie comprimido es una versión avanzada del trie estándar.
3. Sufijo Trie : Un sufijo Trie es una versión avanzada del Trie comprimido.
Con Trie, podemos insertar y encontrar cadenas en el tiempo O (L) donde L representa la longitud de una sola palabra. Esto es obviamente más rápido que BST. Esto también es más rápido que el hashing debido a las formas en que se implementa. No necesitamos calcular ninguna función hash. Otra ventaja de Trie es que podemos imprimir fácilmente todas las palabras en orden alfabético que no es fácilmente posible con el hashing.
La programación dinámica es una técnica que divide los problemas en subproblemas y guarda el resultado para fines futuros para que no necesitemos calcular el resultado nuevamente. Los subproblemas están optimizados para optimizar la solución general se conoce como propiedad de subestructura óptima. El uso principal de la programación dinámica es resolver problemas de optimización. Aquí, los problemas de optimización significan que cuando intentamos averiguar la solución mínima o máxima de un problema. La programación dinámica garantiza encontrar la solución óptima de un problema si existe la solución.
Algoritmo de complejidad del tiempo o (1) Mirando un elemento específico en una matriz, como este, por ejemplo: imprimir (my_array [97]) No importa el tamaño de la matriz, se puede buscar un elemento directamente, solo requiere una operación. (Por cierto, este no es realmente un algoritmo, pero puede ayudarnos a comprender cómo funciona la complejidad del tiempo).
O (n) encontrar el valor más bajo. El algoritmo debe hacer n operaciones en una matriz con n valores para encontrar el valor más bajo, porque el algoritmo debe comparar cada valor una vez.
O (n 2) clasificación de burbujas, clasificación de selección y clasificación de inserción son algoritmos con esta complejidad de tiempo. La razón de sus complejidades de tiempo se explica en las páginas de estos algoritmos.
Grandes conjuntos de datos ralentizan estos algoritmos significativamente. Con solo un aumento en N de 100 a 200 valores, ¡el número de operaciones puede aumentar hasta en 30000!
O (n log n) El algoritmo QuickSort es más rápido en promedio que los tres algoritmos de clasificación mencionados anteriormente, con O (N log n) es el promedio y no el peor de los casos. El peor de los casos para Quicksort también es O (n 2), pero es el tiempo promedio lo que hace que Quicksort sea tan interesante. Aprenderemos sobre Quicksort más tarde.
La referencia se toma de este enlace: ¿Sourav Saini?
