Modelo abstracto de máquina secuencial para el análisis de algoritmos que representa un procesador que opera sobre un arreglo no acotado de celdas de memoria, cada una accesible en tiempo unitario por dirección, y un conjunto estándar de operaciones primarias; usado para estudiar complejidad temporal y espacial bajo la suposición de costo unitario en aritmética y acceso a memoria en tiempo constante.

Principio

Tratar los pasos algorítmicos como operaciones de un procesador central con acceso indexado a memoria en tiempo constante y un conjunto fijo de instrucciones, aislando el coste algorítmico de consideraciones físicas del almacenamiento.

Demostración

Analizar un algoritmo de ordenación de enteros contando el número de operaciones primarias (comparaciones, asignaciones, cargas/almacenamientos) ejecutadas en una RAM con direccionamiento directo; expresar el tiempo de ejecución como función del tamaño de entrada asumiendo que cada acceso a memoria cuesta una unidad de tiempo.

Aplicación incorrecta

Asumir acceso en tiempo unitario para enteros arbitrariamente grandes almacenados en una sola celda sin considerar su longitud en bits, o trasladar costos de la RAM directamente a arquitecturas reales con cachés jerárquicos y latencias no uniformes.

Consecuencia

Proporciona un modelo simple y tratable analíticamente que produce cotas asintóticas independientes de la máquina para tiempo y espacio de algoritmos secuenciales, facilitando la comparación entre algoritmos.

Inversión

Un modelo que considera la memoria como de acceso estrictamente secuencial (por ejemplo, una cinta de máquina de Turing) donde acceder a la i-ésima celda puede requerir tiempo proporcional a i, invirtiendo la suposición de acceso aleatorio.

Límite

No modela computación paralela o distribuida, jerarquías de caché ni efectos de hardware de bajo nivel; las convenciones varían sobre si la aritmética en enteros no acotados tiene costo unitario; excluye recursos estocásticos o cuánticos.

Tensión semántica

Compite con el modelo de máquina de Turing (movimientos finos de cabeza y cinta) y variantes word-RAM (tamaño de palabra acotado), donde difieren las nociones de coste y unidad de memoria.

Síntesis

Un modelo simplificado de computación secuencial que asume acceso indexado a memoria en tiempo constante y operaciones primarias para centrarse en el coste algorítmico mientras abstrae detalles de hardware, adecuado para análisis asintótico cuando se aceptan supuestos de coste unitario.