Wondershare EdrawMind
MindMap Gallery Conceptos básicos de estructuras de datos y algoritmos.
- 1
Conceptos básicos de estructuras de datos y algoritmos.
Introdujo los dos aspectos principales de la estructura de datos y el algoritmo. Las estructuras de datos incluyen principalmente estructuras lineales y estructuras no lineales. Las estructuras lineales incluyen listas lineales, pilas, colas, cadenas, matrices, matrices, listas generalizadas, etc. Las estructuras no lineales incluyen árboles, árboles binarios, bosques, gráficos, etc. Las operaciones de las estructuras de datos incluyen principalmente búsqueda y clasificación. En términos de algoritmos, introduce principalmente algoritmos convencionales como el método de dividir y conquistar, el método de programación dinámica, etc., así como algoritmos de minería de datos, algoritmos de optimización inteligente, etc.
Edited at 2022-06-30 12:23:27
Conceptos básicos de estructuras de datos y algoritmos.
- Recommended to you
- Outline
![[Notas de estudio] Árbol de estructura de datos](https://edrawcloudpublicus.s3.amazonaws.com/work/5169481/2024-5-21/1716254864/thumb.png?x-oss-process=image/resize,w_300,m_lfit)
Notas de puntos de conocimiento de cola de pila de tabla lineal de estructura de datos
- 1
estructura de datos
estructura de datos
concepto
definición
Es una colección de elementos de datos y la relación entre los elementos y el método de construcción.
La relación entre elementos es la estructura lógica de los datos.
El almacenamiento de elementos de datos y las relaciones entre elementos se denomina estructura de almacenamiento (/ estructura física)
Tres elementos
estructura lógica
estructura de almacenamiento
Operación
Clasificar según estructura lógica.
estructura lineal
estructura no lineal
estructura de árbol
estructura grafica
Acerca de la "estructura lineal"
definición
Se utiliza para describir las relaciones de datos con un único predecesor y sucesor en el mundo objetivo.
Características
Existe una relación lineal entre los elementos de datos, es decir, los elementos están dispuestos "uno tras otro"
Clasificación
mesa lineal
definición
Es una secuencia finita de n (n≥0) elementos (estructuralmente indivisibles), generalmente expresada como (a1,a2,...,an)
Operaciones básicas
insertar
borrar
Encontrar
estructura de almacenamiento
almacenamiento secuencial
Utilice un conjunto de unidades de almacenamiento con direcciones consecutivas para almacenar secuencialmente elementos de datos en la tabla lineal
La ubicación de almacenamiento del i-ésimo elemento ai.
LOC(ai) = LOC(a1) (i-1) x L
almacenamiento en cadena
Almacene elementos de datos utilizando nodos vinculados por punteros
estructura de nodo
campo de datos
Se utiliza para almacenar el valor del elemento de datos.
campo de puntero
Se utiliza para almacenar la información de posición del predecesor inmediato o sucesor inmediato del elemento actual.
Clasificación
Lista enlazada lineal (o lista enlazada unidireccional)
Solo hay un campo de puntero en el nodo.
lista doblemente enlazada
Cada nodo tiene 2 punteros.
lista circular enlazada
El puntero del nodo al final de la tabla apunta al nodo al principio de la tabla.
lista enlazada estática
Utilice matrices para describir la estructura de almacenamiento vinculada de listas lineales
pila
definición
El almacenamiento y la recuperación de datos solo se pueden lograr a través de un extremo (LIFO, Last In First Out, LIFO)
Operaciones básicas
Pila de inicialización InitStack(S)
Determinar que la pila está vacía IsEmpty(S)
Empujar a la pila Empujar (S, x)
pop(s)
Leer el elemento superior de la pila Top(S)
estructura de almacenamiento
almacenamiento secuencial
almacenamiento en cadena
solicitud
Evaluación de expresiones
coincidencia de soportes
Convertir un proceso recursivo en un proceso no recursivo
cola
definición
Los elementos solo se pueden insertar en un extremo de la tabla y eliminar en el otro extremo de la tabla (primero en entrar, primero en salir, FIFO)
Operaciones básicas
Inicializar la cola InitQueue(Q)
Equipo de jueces vacío IsEmpty(Q)
En cola En cola (Q, x)
Quitar cola DelQueue(Q)
Leer el elemento principal de la cola FrontQue(Q)
estructura de almacenamiento
almacenamiento secuencial
cola secuencial
cola circular
almacenamiento en cadena
cola de cadena
cadena
definición
Sólo una secuencia limitada de caracteres. Generalmente registrado como S = 'a1a2...an', S es el nombre de la cadena y la cadena después de = es el valor de la cadena.
concepto basico
Cadena vacía; cadena espacial; comparación de cadenas; subcadena;
Operaciones básicas
Operación de asignación StrAssign(s, t)
Operación de concatenación Concat(s, t)
Longitud de cadena StrLength(s)
Comparación de cadenas StrCompare(s, t)
Buscar subcadena SubString(s, start, len)
estructura de almacenamiento
almacenamiento secuencial
almacenamiento en cadena
la coincidencia de patrones
definición
La operación de posicionamiento de subcadenas se denomina coincidencia de patrones de cadena.
La subcadena también se llama cadena de patrón.
algoritmo de coincidencia
Algoritmo ingenuo de coincidencia de patrones
Algoritmo Brut-Foss
Algoritmo de coincidencia de patrones mejorado
algoritmo KMP
promoción
formación
definición
Una matriz es una extensión de una lista lineal de longitud fija en términos de dimensiones, es decir, los elementos de una lista lineal también son una lista lineal.
Una matriz N-dimensional es una estructura de datos "isomorfa", en la que cada elemento de datos tiene el mismo tipo y estructura consistente.
Características
Número fijo de elementos de datos.
Los elementos de datos son del mismo tipo.
La relación de subíndices de los elementos de datos tiene restricciones de límite superior e inferior, y los subíndices están ordenados
Operaciones básicas
Dado un conjunto de subíndices, acceda a los elementos de datos.
Dado un conjunto de subíndices, modifique el elemento de datos.
estructura de almacenamiento
almacenamiento secuencial
matriz
definición
Una matriz es un objeto matemático. Aquí estudiamos principalmente cómo hacer que varias operaciones en la matriz se ejecuten de manera eficiente mientras se ahorra espacio de almacenamiento.
Clasificación
matriz especial
La distribución de elementos con el mismo valor o 0 elementos en la matriz tiene ciertas reglas.
Clasificación
matriz simétrica
matriz diagonal
matriz triangular
matriz dispersa
Los elementos con el mismo valor o 0 elementos se distribuyen irregularmente en la matriz
almacenamiento
Utilice triplete (i, j, aij) para almacenar el número de fila, el número de columna y el valor de 1 elemento
estructura de almacenamiento
almacenamiento secuencial
tabla de secuencia triple
almacenamiento en cadena
lista cruzada
tabla generalizada
definición
es una secuencia finita que consta de 0 o más elementos individuales o sublistas
longitud
numero de elementos
profundidad
El número máximo de niveles de corchetes contenidos en una tabla generalizada después de la expansión.
Operaciones básicas
insertar
borrar
Encontrar
estructura de almacenamiento
almacenamiento en cadena
Acerca de la "estructura no lineal"
Árbol
definición
Un elemento de datos puede tener de cero a un elemento predecesor inmediato y dos o más elementos sucesores inmediatos.
Un árbol es un conjunto finito de n(n≥0) nodos
La definición de árbol es recursiva. Sólo hay un nodo llamado "raíz" y los nodos restantes se denominan "subárboles" del nodo raíz.
estructura lógica
Existe una relación jerárquica entre elementos.
concepto basico
padres
El nodo raíz del nodo hijo.
niño
La raíz del subárbol de un nodo se denomina hijo del nodo.
hermano
Los nodos con los mismos padres son hermanos entre sí.
nodo hoja
Nodo terminal, el grado es 0
nodo interno
Nodo no terminal o nodo ramal, el grado no es 0
grado de nodo
El número de subárboles de un nodo.
Nivel de nodo
La raíz es el nivel 1, los hijos de la raíz son el nivel 2, y así sucesivamente.
altura del arbol
El número máximo de capas en un árbol se registra como la altura (o profundidad) del árbol.
Árboles ordenados y desordenados.
Si los subárboles de los nodos del árbol están ordenados, es un árbol ordenado; de lo contrario, es un número desordenado.
estructura de almacenamiento
representación de los padres
representación infantil
representación del hermano menor
Proporciona la posibilidad de realizar conversiones entre árboles, árboles binarios y bosques.
Operaciones básicas
atravesar
Forma
Primero el recorrido de la raíz.
Primero visite el nodo raíz del árbol y luego recorra cada subárbol de la raíz en secuencia.
recorrido de la raíz posterior
Primero recorra cada subárbol de la raíz en secuencia y luego visite el nodo raíz.
Otros segmentos
Árbol binario
definición
Un árbol binario es un conjunto finito de n(n≥0) nodos
La definición de árbol binario es recursiva. Se compone de 1 nodo raíz y 2 árboles binarios separados llamados subárboles izquierdo y derecho respectivamente.
Propiedades principales
Hay como máximo 2 (i-1) nodos de potencia en el i-ésimo nivel (i≥1) del árbol binario
Un árbol binario con altura k (k≥1) tiene como máximo 2 k-1 nodos.
Clasificación
árbol binario completo
No hay nodos vacíos en cada capa.
árbol binario completo
Excepto el último piso, todos los demás pisos están llenos.
Los nodos de la última capa se colocan de izquierda a derecha y no se pueden dejar en blanco.
árbol binario no completo
estructura de almacenamiento
almacenamiento secuencial
Almacene los nodos del árbol binario en un orden apropiado en un conjunto de celdas de memoria con direcciones consecutivas.
Suponga un árbol binario completo con el nodo raíz número 1. Si hay un nodo numerado i, entonces
Si i=1, entonces el nodo es el nodo raíz y no tiene padres.
Si i>1, entonces el nodo padre de este nodo es ⌊ i/2 ⌋
Si 2i≤n, entonces el hijo izquierdo del nodo es 2i; de lo contrario, no hay hijo izquierdo
Si 2i 1≤n, entonces el hijo derecho del nodo es 2i 1; de lo contrario, no hay hijo derecho
almacenamiento en cadena
almacenamiento
El nodo contiene elementos de datos, padres, la raíz del subárbol izquierdo y la raíz del subárbol derecho.
Disponible almacenamiento de lista enlazada binaria o lista triple enlazada
Operaciones básicas
atravesar
definición
El proceso de visitar cada nodo del árbol de acuerdo con una determinada estrategia y visitarlo solo una vez.
El proceso de atravesar un árbol binario es esencialmente un proceso de organizar los nodos del árbol en una secuencia lineal de acuerdo con ciertas reglas.
Forma
(1) De acuerdo con la convención de atravesar primero el subárbol izquierdo y luego el subárbol derecho, dependiendo de la ubicación del nodo raíz visitado,
3 formas disponibles
recorrido de preorden
recorrido en orden
recorrido posterior al pedido
(2) Recorrido del orden de las capas (acceso de arriba hacia abajo, de izquierda a derecha, capa por capa)
Otros segmentos
árbol binario de pistas
definición
En la información de almacenamiento de los nodos del árbol binario, agregue información del predecesor directo y del sucesor directo.
árbol binario óptimo
definición
También conocido como árbol de Huffman, es un árbol con la longitud de camino ponderada más corta.
concepto basico
camino
Un camino de un nodo a otro en el árbol.
longitud de la trayectoria
Número de ramas en el camino.
longitud de ruta ponderada del nodo
La longitud del camino desde el nodo hasta la raíz del árbol multiplicada por el peso del nodo.
longitud del camino del árbol
La suma de las longitudes de los caminos desde la raíz hasta cada hoja.
La longitud del camino ponderado del árbol.
La suma de las longitudes de ruta ponderadas de todos los nodos de hojas en el árbol.
Algoritmo de construcción
(1) En el conjunto de árboles binarios, seleccione los dos árboles con el peso más pequeño como subárboles izquierdo y derecho (el que tiene el peso más pequeño de los dos se coloca como el subárbol izquierdo) para construir un nuevo árbol binario Los nodos raíz. de los subárboles izquierdo y derecho son La suma de los pesos de los puntos se utiliza como el peso del nodo raíz del nuevo árbol binario; (2) Elimine estos dos árboles del conjunto y agregue el árbol recién construido; Repita los pasos anteriores;
solicitud
Codificación Huffman
ilustrar
bosque
definición
Los árboles y los bosques se definen mutuamente de forma recursiva.
Operaciones básicas
atravesar
Forma
recorrido de preorden
Primero visite el nodo raíz del primer árbol del bosque y luego recorra el bosque del subárbol del nodo raíz del primer árbol en orden. La última orden atraviesa el bosque de árboles restantes.
recorrido en orden
Primero recorra en orden el bosque de subárbol del primer árbol del bosque y luego visite el nodo raíz del primer árbol. Finalmente, en orden atraviesa el bosque compuesto por los árboles restantes.
Conversión entre árboles, árboles binarios y bosques.
Convertir árbol en árbol binario
paso
(1) Agregar una línea: agregar una conexión entre nodos hermanos
(2) Eliminación de línea: el nodo solo conserva la conexión con el primer nodo
(3) Ajuste de nivel (rotación): con el nodo raíz del árbol como eje, gire para que el primer nodo secundario esté ubicado en la posición secundaria izquierda y el nodo hermano esté ubicado en la posición secundaria derecha.
Convertir bosque en árbol binario
paso
(1) Cada árbol del bosque se convierte en un árbol binario.
(2) El primer árbol binario no se mueve y el nodo raíz del siguiente árbol binario se utiliza como el hijo derecho del nodo raíz del árbol binario anterior y se conecta.
Convertir árbol binario en árbol
paso
(1) Agregue una línea: n nodos secundarios derechos del hijo izquierdo de un nodo son todos nodos secundarios de este nodo y están conectados.
(2) Eliminación de línea: elimine las conexiones entre todos los nodos en el árbol binario original y sus nodos secundarios derechos
(3) Ajuste de nivel (rotación)
Convertir árbol binario en bosque
paso
(1) Separar el árbol binario
Comenzando desde el nodo raíz, elimine todas las conexiones secundarias correctas.
(2) Convertir árbol binario en árbol
imagen
definición
No hay límite para el número de nodos predecesores y nodos sucesores de un nodo.
Graph G(Graph) es una tupla que consta de conjuntos V(Vertex) y E(Edge), denotada como G=(V, E)
V es un conjunto finito no vacío de vértices (elementos de datos)
E es un conjunto finito de aristas (relaciones entre elementos de datos)
concepto basico
grado de vértice
Gastar
El número de aristas asociadas con el vértice es la suma de los grados de entrada y de salida, denotado D(v)
grado
es el número de aristas dirigidas que terminan en el vértice, registrado como ID(v)
grado
Es el número de aristas dirigidas a partir de este vértice, registrado como OD(v)
camino
Secuencia de vértices desde el vértice vp hasta el vértice vq
longitud de la trayectoria
número en el camino
bucle o anillo
El camino donde el primer vértice y el último vértice son iguales
Si los vértices restantes del camino son diferentes, se llama camino simple.
subtrama
Gráficos conectados y componentes conectados.
gráfico conectado
Dos vértices cualesquiera son gráficos no dirigidos conectados
componentes conectados
Subgrafo máximamente conectado de este gráfico
Gráfico fuertemente conectado y componentes fuertemente conectados
Gráfico fuertemente conectado
Dos vértices cualesquiera son gráficos dirigidos conectados
Componente fuertemente conectado
Subgrafo máximamente conectado de este gráfico
neto
Gráfico con pesos laterales
árbol dirigido
Un gráfico dirigido con un vértice con un grado de entrada de 0 y los vértices restantes con un grado de entrada de 1
árbol de expansión
Subgrafo mínimo conectado del gráfico (sin ciclos)
El árbol de expansión de un gráfico no es único
Ruta más corta del punto de origen único
Clasificación
gráfico dirigido
Cada borde tiene una dirección.
La relación entre vértices está representada por <vi, vj>
Significa que vi a vj tiene un borde dirigido (también llamado arco)
vi es el punto inicial del borde dirigido, llamado cola del arco
vj es el punto final del borde dirigido, llamado cabeza de arco
Otros segmentos
Gráfico Acíclico Dirigido
Gráfico dirigido sin ciclos.
Gráfico no dirigido
Cada borde no tiene dirección
La relación entre vértices está representada por (vi, vj)
grafico completo
Cada vértice tiene una arista con otros vértices.
Clasificación
Gráfico completo dirigido
gráfico completo no dirigido
estructura de almacenamiento
Notación matricial de adyacencia
Representación de lista enlazada de adyacencia
Operaciones básicas
atravesar
definición
El recorrido del gráfico se refiere al proceso de comenzar desde un determinado vértice y visitar todos los vértices del gráfico a lo largo de una determinada ruta de búsqueda solo una vez.
Forma
Primera búsqueda en profundidad (DFS)
Busque y acceda en profundidad primero si es posible
Primera búsqueda en amplitud (BFS)
Intente buscar primero en dirección horizontal si es posible
Acerca del "árbol de expansión mínimo"
definición
Para una red conectada, los bordes están ponderados y cada borde del árbol de expansión también está ponderado.
El árbol de expansión mínimo es el árbol de expansión con el peso más pequeño.
concepto basico
Árbol de expansión a la derecha
La suma de los pesos de cada borde del árbol de expansión.
Algoritmos de resolución de árbol de expansión mínima comúnmente utilizados
algoritmo de primi
algoritmo de Kruskal
Acerca del "camino más corto desde una única fuente"
definición
Significa que dado un gráfico dirigido ponderado G y un punto fuente v0, encuentre el camino más corto desde v0 hasta los vértices restantes en G
Algoritmos de resolución comúnmente utilizados
algoritmo de dijkstra
algoritmo de floyd
solicitud
Red AOV (red Actividad en Vertex)
definición
Un gráfico dirigido que utiliza vértices para representar actividades y bordes dirigidos para representar relaciones de prioridad entre actividades.
Los ciclos dirigidos no deberían aparecer en la red AOV
Compruebe si hay un bucle en la red AOV
método
Para un gráfico dirigido, construya una secuencia topológicamente ordenada de sus vértices. Si todos los vértices del gráfico están en su secuencia topológicamente ordenada, no hay ciclo.
paso
(1) Seleccione un vértice en la red con un grado de entrada de 0 y envíelo
(2) Eliminar el vértice y todos los arcos asociados de la red
(3) Repita los dos pasos anteriores hasta que no haya vértices con un grado de entrada de 0 en la red.
(4) Resultado
Si se han generado todos los vértices, se completa toda la clasificación topológica, lo que indica que no hay ningún bucle.
Si todavía hay vértices que no se han generado y los vértices restantes tienen vértices predecesores, la clasificación topológica no puede continuar en este momento, lo que indica que hay un bucle.
Red AOE (red de actividad en el borde)
definición
Un gráfico dirigido en el que los eventos están representados por vértices, las actividades están representadas por aristas dirigidas y la duración de la actividad está representada por los pesos en las aristas.
El tiempo requerido para todo el proyecto es la longitud del camino más largo desde el vértice inicial hasta el vértice final.
concepto basico
El evento representado por el vértice es una señal de que algunas actividades se han completado y otras se pueden iniciar.
Fuente
El vértice inicial con grado 0.
punto de encuentro
Vértice final sin grado 0
Camino critico
El camino más largo desde la fuente hasta el sumidero
Todas las actividades en la ruta crítica son actividades críticas.
La hora del evento de vértice.
El momento de aparición más temprana del evento de vértice ve(j)
La última hora de aparición del evento de vértice vl(i)
Operaciones sobre estructuras de datos.
Encontrar
concepto basico
ilustrar
La búsqueda es una operación básica de uso común.
tabla de búsqueda
Se refiere a una colección de elementos de datos (o registros) del mismo tipo.
Palabras clave
¿Es el valor de un elemento de datos de un elemento de datos (o registro)?
Se utiliza para identificar (identificar) este elemento de datos.
palabra clave principal
Una palabra clave que identifica de forma única un elemento de datos.
palabras clave secundarias
se refiere a una palabra clave que puede identificar múltiples elementos de datos
Resultados de la búsqueda
Búsqueda exitosa
La búsqueda falló
longitud media de búsqueda
El número esperado de veces que es necesario comparar el proceso de búsqueda con el valor de palabra clave dado.
Operaciones básicas de tablas de búsqueda.
tabla de búsqueda estática
Consultar si un determinado elemento de datos está en la tabla de búsqueda
Recuperar varios atributos de un elemento de datos.
tabla de búsqueda dinámica
Insertar un elemento de datos
Eliminar un elemento de datos
Acerca de la "Tabla de búsqueda estática"
encontrar método
Clasificación
búsqueda secuencial
media búsqueda
Análisis de proceso
El proceso de búsqueda se puede describir mediante un árbol binario.
Método de construcción del árbol de decisión de búsqueda binaria (binario)
(1) Tome el número de la posición media del intervalo de búsqueda actual como raíz
(2) Los números de serie de registros en la mitad izquierda de la subtabla y la mitad derecha de la subtabla se utilizan como nodos en el subárbol izquierdo y el subárbol derecho de la raíz, respectivamente.
Buscar en trozos
Acerca de la "Tabla de búsqueda dinámica"
Características
La estructura de la tabla en sí se genera dinámicamente durante el proceso de búsqueda.
Clasificación de la estructura de la tabla.
árbol de clasificación binaria
definición
También conocido como árbol de búsqueda binaria.
puede ser un árbol vacío
O un árbol binario con las siguientes propiedades
Si el subárbol izquierdo no está vacío, entonces los valores de todos los nodos en el subárbol izquierdo son menores que el valor del nodo raíz.
Si el subárbol derecho no está vacío, entonces los valores de todos los nodos en el subárbol derecho son mayores que el valor del nodo raíz.
Los propios subárboles izquierdo y derecho son árboles ordenados binariamente.
árbol binario equilibrado
definición
También conocido como árbol AVL.
puede ser un árbol vacío
O un árbol binario con las siguientes propiedades
El valor absoluto de la diferencia entre las alturas de los subárboles izquierdo y derecho no excede 1
Los subárboles izquierdo y derecho son árboles binarios equilibrados.
funcionar
insertar
Tratamiento de equilibrio derecho unidireccional tipo LL
Tratamiento de equilibrado unidireccional tipo RR a izquierdas
Procesamiento de equilibrio de rotación bidireccional primero a la izquierda y luego a la derecha tipo LR
Tipo RL primero a la derecha y luego a la izquierda procesamiento de equilibrio de rotación bidireccional
B_árbol de orden m
definición
puede ser un árbol vacío
O un árbol m con las siguientes propiedades
Cada nodo del árbol tiene como máximo m subárboles.
...
árbol negro rojo
Tabla hash (o tabla hash)
definición
La dirección de almacenamiento del registro se obtiene calculando una función (llamada función hash) con la clave del registro como variable independiente.
Es decir, según la función hash establecida H (clave) y el método de manejo de conflictos, un conjunto de palabras clave se asigna a un conjunto de direcciones continuo limitado (intervalo) y la "imagen" de la palabra clave en el conjunto de direcciones se utiliza como una ubicación de almacenamiento de registros en la tabla.
Este proceso de mapeo se llama hash o hash.
La ubicación de almacenamiento resultante se denomina dirección hash o dirección hash.
concepto basico
Acerca de las colisiones de hash
Para una determinada función hash H y las dos claves K1 y K2, si K1≠K2 y H(K1)=H(K2), se llama conflicto
Las palabras clave con el mismo valor de función hash se denominan sinónimos de esa función hash.
Generalmente hablando
Las colisiones solo se pueden reducir tanto como sea posible, pero no evitarlas por completo, porque la función hash es la imagen desde el conjunto de palabras clave hasta el conjunto de direcciones.
La función hash es una imagen comprimida y las colisiones son inevitables.
Principales cuestiones a considerar
Cómo construir una función hash
Métodos comunes
método de direccionamiento directo
analítica digital
Método cuadrado-medio
método de plegado
método de números aleatorios
método de división dejando resto
Problemas que deben resolverse
La función hash debe ser una función de imagen comprimida, que debe tener una mayor compresión para ahorrar espacio de almacenamiento.
La función hash debe tener buenas propiedades de hash y asignar palabras clave a varias unidades de almacenamiento en el área de almacenamiento de la manera más uniforme posible.
Cómo resolver conflictos
Métodos comunes
método de direccionamiento abierto
método de dirección de cadena
refrito
Crear un área de desbordamiento pública
Operaciones básicas
Encontrar
concepto
Calcule la dirección de almacenamiento del registro que se va a verificar utilizando la misma función hash y método de manejo de conflictos que se usa al almacenar elementos.
longitud media de búsqueda
Dependiendo de
Función hash
Cómo manejar los conflictos
Factor de relleno de la tabla hash
Acerca del "Factor de llenado de la tabla hash"
definición
α = número de registros cargados en la tabla / longitud de la tabla hash
clasificar
concepto basico
definición
Supongamos que el contenido del archivo que contiene n registros es {R1, R2,…,R} y las palabras clave correspondientes son {k1,k2,…,kn}. Después de la clasificación, se determina una disposición {Rj1, Rj2,…,Rjn}, Haga que sus palabras clave satisfagan la siguiente relación creciente (o decreciente): kj1≤kj2≤...≤kjn (o kj1≥kj2≥...≥kjn).
Estabilidad del método de clasificación.
Método de clasificación estable
Graba Ri y Rj con la misma palabra clave, Ri está por delante de Rj. Después de la clasificación, el orden de Ri y Rj permanece sin cambios.
Método de clasificación inestable
Graba Ri y Rj con la misma palabra clave, Ri está por delante de Rj. Después de la clasificación, el orden de Ri y Rj puede cambiar
Operaciones básicas
(1) Compare el tamaño de las palabras clave;
(2) Dependiendo del método de almacenamiento, es posible que sea necesario mover la ubicación del registro;
Clasificación
Clasificación interna
clasificación sencilla
clasificación por inserción directa
Ordenamiento de burbuja
Orden de selección simple
clasificación de colinas
clasificación de montón
Ordenación rápida
fusionar ordenar
clasificación de combinación bidireccional
Ordenación por base
clasificación externa
método básico
Clasificación del método
fusión equilibrada de k-way
algoritmo
concepto basico
Investigación de la teoría de algoritmos
Técnicas de diseño de algoritmos (/estrategia)
Responda la pregunta: "¿Cómo idear un algoritmo para resolver un problema específico?"
Técnicas de análisis algorítmico
Responda la pregunta: "¿Es el algoritmo lo suficientemente bueno?"
definición
Un algoritmo es una descripción de los pasos para resolver un problema específico. Es una secuencia finita de instrucciones. Cada una de estas instrucciones representa una o más operaciones.
5 características importantes de los algoritmos
finitud
certeza
factibilidad
ingresar
producción
Acerca del "diseño de algoritmos"
Técnica principal
Método de dividir y conquistar, método de programación dinámica, método codicioso, método de retroceso, método de rama y límite, algoritmo de probabilidad, algoritmo de aproximación
Acerca del "Análisis algorítmico"
algunos criterios analíticos
Corrección, confiabilidad, simplicidad y comprensibilidad del algoritmo.
La complejidad temporal y espacial del algoritmo.
Representación de algoritmos
lenguaje natural
diagrama de flujo
lenguaje de programación
pseudocódigo
Acerca de la "complejidad del tiempo"
analizar
definición
Analiza principalmente el tiempo de ejecución del algoritmo, es decir, la cantidad de operaciones básicas necesarias para la ejecución del algoritmo.
método
Establezca una función T (n) con la escala de entrada n como variable independiente para representar la complejidad temporal del algoritmo.
Según diferentes entradas, hay 3 situaciones.
en el mejor de los casos
peor de los casos
situación promedio
símbolo progresivo
es una abstracción adicional del método T(n) anterior, que solo considera la tasa de crecimiento del tiempo de ejecución (o llamada magnitud de crecimiento)
Método analítico
oh marca
Análisis asintótico del límite superior
ejemplo:
símbolo Ω
Próximo análisis gradual
símbolo Θ
Análisis de límite superior asintótico y de límite inferior asintótico, es decir, análisis de límite compacto asintótico
Estructura del algoritmo
Generalmente se puede dividir en
forma no recursiva
forma recursiva
Principales métodos de análisis de la complejidad del tiempo.
método de expansión
método de sustitución
método de árbol recursivo
método principal
Algoritmo convencional
divide y conquistaras
Idea básica
Descomponer un problema grande que es difícil de resolver directamente en varios problemas idénticos más pequeños para que puedan descomponerse individualmente y dividirse y conquistarse.
recursividad
Significa que la subrutina se llama a sí misma directa o indirectamente mediante una serie de declaraciones de llamada.
Elementos basicos
Condiciones de borde
modo recursivo
Los pasos principales
Los pasos del algoritmo divide y vencerás en cada nivel de recursividad
(1) Descomposición
(2) Resolver
(3) Fusionar
solicitud
fusionar ordenar
Máximo de campos y preguntas
programación dinámica
Idea básica
Divida un problema grande que sea difícil de resolver directamente en varios problemas idénticos más pequeños y ataque cada uno de ellos. A diferencia del enfoque de divide y vencerás, los subproblemas a menudo no son independientes
Guarde las respuestas a los subproblemas resueltos en una tabla y recupérelas cuando sea necesario
Los pasos principales
(1) Descubra las propiedades de la solución óptima.
(2) Definir recursivamente el valor de la solución óptima.
(3) Calcule el valor óptimo de abajo hacia arriba
(4) Construya una solución óptima basada en la información obtenida al calcular el valor óptimo.
solicitud
0-1 problema de mochila
Subsecuencia común más larga (LCS)
método codicioso
Idea básica
La estrategia consiste en tomar decisiones basadas únicamente en la información actualmente disponible y obtener soluciones óptimas locales (/aproximadas).
forma de algoritmo
algoritmo recursivo codicioso
algoritmo iterativo codicioso
solicitud
Problemas de selección de actividades
problema de mochila
Retroceder
Idea básica
Después de determinar la estructura organizativa del espacio de la solución, el método de retroceso comienza desde el nodo inicial (nodo raíz) y busca en todo el espacio de la solución primero en profundidad. Hasta que se encuentre la solución requerida o no haya nodos activos en el espacio de la solución
El objetivo de la solución es encontrar todas las soluciones que satisfagan las restricciones.
espacio de solución
Debe contener al menos una solución (óptima) al problema.
Generalmente expresado en forma de árbol o gráfico.
función delimitadora
Dado que el espacio de la solución suele ser muy grande, para realizar una búsqueda eficaz, es necesario podar algunos nodos durante el proceso de búsqueda. Diseñar una función delimitadora para el juicio de poda (podar lo antes posible y tanto como sea posible)
Los pasos principales
(1) Definir el espacio de solución del problema.
(2) Determine la estructura del espacio de soluciones que sea fácil de buscar.
(3) Busque el espacio de la solución primero en profundidad
marco de puntuación
forma recursiva
no recursivo
solicitud
0-1 problema de mochila
n problema de la reina
método de rama y enlace
Idea básica
Similar al método de retroceso, también es un algoritmo que busca la solución al problema en el árbol del espacio de soluciones T del problema.
Busque el espacio de la solución primero en amplitud o con el menor costo primero
El objetivo de la solución es encontrar una solución (óptima) que satisfaga las restricciones
función delimitadora
Clasificados según diferentes formas de seleccionar el siguiente nodo de expansión de la tabla de puntos activos
Método de bifurcación y enlace en cola (FIFO, primero en entrar, primero en salir)
rama de cola prioritaria y método vinculado
Algoritmo probabilístico
Idea básica
Cuando el algoritmo realiza ciertos pasos, se puede elegir aleatoriamente cómo proceder a continuación, permitiendo al mismo tiempo que los resultados sean erróneos con una probabilidad menor y, a expensas de esto, obtener una reducción sustancial en el tiempo de ejecución del algoritmo.
Clasificación
Algoritmo de probabilidad numérica
Algoritmo de Montecarlo
Algoritmo de Las Vegas
Algoritmo de Sherwood
algoritmo de aproximación
Idea básica
Dejar de buscar la solución óptima y reemplazar la solución óptima con una solución óptima aproximada a cambio de simplificar el diseño del algoritmo y reducir la complejidad del tiempo.
Medida de desempeño
La complejidad temporal del algoritmo.
El grado de aproximación de la solución.
algoritmo de minería de datos
procesamiento de datos
concepto basico
Es una materia interdisciplinaria que utiliza métodos de aprendizaje automático para analizar y extraer una variedad de datos (datos de bases de datos, datos de almacenes de datos, datos web, etc.)
centro
es un algoritmo
La función principal
Clasificación
devolver
reglas de asociación
agrupamiento
Algoritmo de optimización inteligente
Descripción general
Tecnología de optimización
Es una tecnología de aplicación basada en las matemáticas y utilizada para resolver soluciones óptimas a diversos problemas de ingeniería.
En el campo de la optimización, debido a la intuición y el mecanismo natural de estas construcciones algorítmicas, a menudo se les denomina "algoritmos de optimización inteligentes" o "algoritmos heurísticos modernos".
Algoritmos de optimización existentes
Red neuronal artificial (RNA)
principio
Un sistema dinámico con una topología de grafo dirigido que procesa información respondiendo a estados de entrada continuos o discontinuos.
Clasificación
Redes de retroalimentación y retroalimentación
Clasificación
Red neuronal directa multicapa basada en el algoritmo BP
aprendizaje automático profundo
Redes de creencias profundas (DBN)
Redes neuronales convolucionales (CNN)
algoritmo genético
Algoritmo de recocido simulado (SA)
Algoritmo de búsqueda tabú (TS)
Algoritmo de colonia de hormigas
Algoritmo de optimización de enjambre de partículas (PSO)