Algoritmo aleatorio
Para obtener un resumen, consulte /p/60ea83ea17cc
El tiempo de ejecución en el peor de los casos de un algoritmo aleatorio es casi siempre el mismo que el tiempo de ejecución en el peor de los casos de un algoritmo no aleatorio. algoritmo. La diferencia importante es que los buenos algoritmos aleatorios no tienen malas entradas, sólo números aleatorios malos (en relación con una entrada específica).
Por ejemplo: para una clasificación rápida, el método A usa el primer elemento como elemento pivote y el método B usa el elemento seleccionado aleatoriamente como elemento pivote.
Con un algoritmo aleatorio, las entradas específicas ya no importan. Lo que importa son los números aleatorios, y podemos obtener el tiempo de ejecución deseado promediando todos los números aleatorios posibles en lugar de promediar todas las entradas posibles.
Los números aleatorios tienen muchas propiedades estadísticas conocidas; los números pseudoaleatorios satisfacen la mayoría de estas propiedades.
Lo que realmente se necesita es una secuencia de números aleatorios. Estos números deberían aparecer de forma independiente.
Generador de números lineales congruentes
El método más sencillo para generar números aleatorios es el generador de números lineales congruentes, propuesto por Lehmer en 1951:
Por ejemplo: M = 11, x0 = 1
A = 7: 7, 5, 2, 3, 10, 4, 6, 9, 8, 1, 7, 5, 2... (el periodo es 10 = M-1)
A = 5: 5, 3, 4, 9, 1, 5, 3, 4... (el periodo es 5 < M -1)
Un generador de números aleatorios con errores (devuelve un valor en el intervalo abierto (0,1)): desbordamiento multiplicativo
Generador de números aleatorios funcionando en una máquina de 32 bits
Prueba: por qué δ (xi) es 0 o 1
¿Por qué δ(xi)=1 solo cuando el valor del resto es menor que 0?
Explicación: Debido a que aquí hay M resto, entonces si es múltiplo de M, naturalmente se cancelará y ambos términos de δ (xi) son funciones de redondeo, por lo que deben ser números enteros. Además, xi+1 siempre está entre 1 ~ M-1, por lo que el resto. Si es menor que 0, tome 1
El primer uso de la aleatorización es en estructuras de datos que admiten la búsqueda y la inserción en el tiempo esperado O(lgn).
Cada nodo 2^i tiene un puntero que apunta al siguiente nodo 2^i. El número total de punteros solo se duplica, pero ahora se puede examinar un máximo de nodos de piso (lgn) en una búsqueda. punto. Por lo tanto, el consumo de tiempo total es O (lgn).
Esencialmente una búsqueda binaria:
Relajar las condiciones estructurales de la estructura de datos anterior forma una tabla de salto:
¿Si queremos saber si existe 19? ¿Cómo encontrarlo? Comenzamos desde el nodo principal, primero juzgamos con 9, que en este momento es mayor que 9, y luego juzgamos con 21, que es menor que 21. En este momento, el valor debe estar entre el nodo 9 y el nodo 21. En este momento, juzgamos con 17, mayor que 17, y luego lo juzgamos con 21, si es menor que 21, debe estar entre el nodo 17 y el nodo 21 en este momento, luego lo juzgamos con 19 y encontramos él.
1) Implementación
2) Consumo de espacio
3) Búsqueda
Características de implementación de la tabla de salto 1-2-3:
Busque el primer nodo más grande que el elemento en la lista vinculada en el mismo nivel (no más de 3 nodos) y luego muévalo hacia abajo un nivel.
4) Inserción
Se debe asegurar que cuando se agregue un nuevo nodo con altura h, no se creará un espacio con cuatro nodos con altura h.
Insertar método de arriba hacia abajo usando el árbol 2-3-4 (asegúrese de que el nodo actual no sea de 4 nodos): (Referencia/p/8258ed821859)
Establecer en nivel L y quiero bajar al siguiente nivel. Si la capacidad del espacio de la siguiente capa es 3, se eleva el término medio del espacio a su altura L, formando así dos espacios con capacidad de 1. El enchufe es seguro ya que elimina el espacio con una capacidad de 3 al permitir el retiro hacia abajo en la carretera.
5) Eliminar
Eliminar usando el método de arriba hacia abajo del árbol 2-3-4 (asegúrese de que el nodo actual no sea de 2 nodos): (Referencia/p/ 8258ed821859 )
El problema de determinar si un número grande es primo.
Los nodos incluyen:
El nodo con menor prioridad debe ser el raíz. El árbol se forma a partir de N! posibles permutaciones de prioridades en lugar de N!
1) Inserción
Después de la inserción, restaure las propiedades del orden del montón mediante rotación hacia la izquierda y hacia la derecha:
2) Eliminar
Este método de eliminación También puede utilizar el método de eliminación del árbol rojo-negro para reducir la eliminación a la eliminación de nodos hoja.
(use el sucesor, esto ahorra muchos giros)