¿El hardware / implementación afectará la complejidad tiempo / espacio de los algoritmos?

Ni siquiera soy un estudiante de CS, así que esta podría ser una pregunta estúpida, pero por favor tengan paciencia conmigo ...

En la era anterior a la computadora, solo podemos implementar una estructura de datos de matriz con algo así como una matriz de cajones. Dado que uno tiene que ubicar el cajón con el índice correspondiente antes de extraerle el valor, la complejidad temporal de la búsqueda de matriz es , suponiendo una búsqueda binaria.$O(log(n))$

Sin embargo, la invención de las computadoras hizo una gran diferencia. Las computadoras modernas pueden leer desde su RAM tan rápido que ahora consideramos que la complejidad temporal de la búsqueda de matriz es (aunque técnicamente no es el caso, porque lleva más tiempo mover el registro a una distancia mayor, etc.)$O(1)$

Otro ejemplo son los diccionarios Python. Si bien uno puede obtener una complejidad de acceso al diccionario de con un método mágico sobrecargado mal escrito (o ridículamente mala suerte, es decir, claves que tienen muchas colisiones hash), generalmente se presume que es O ( 1 ) . En este caso, la complejidad del tiempo depende tanto de la implementación de la tabla hash de los diccionarios Python como de la implementación de las funciones hash de las teclas.$O(n)$__hash__$O(1)$

¿Esto implica que el hardware / implementación puede afectar la complejidad temporal de los algoritmos? (Si bien ambos ejemplos tratan sobre estructuras de datos en lugar de algoritmos, los últimos se basan en el primero, y nunca he oído hablar de la complejidad temporal de las estructuras de datos, por lo que estoy usando el término "algoritmos" aquí)

Para mí, los algoritmos son abstractos y conceptuales, cuyas propiedades como la complejidad del tiempo / espacio no deberían verse afectadas por si se implementan de una manera específica, pero ¿lo son?

Seguro. Ciertamente. Aquí le mostramos cómo conciliar su incomodidad.

$O(\log n)$$O(1)$

Una vez que haya elegido un modelo de computación, el análisis del algoritmo es un ejercicio matemático puramente abstracto, conceptual, que ya no depende del hardware.

Sin embargo, en la práctica, generalmente queremos elegir un modelo de cálculo que refleje la realidad de nuestro hardware, al menos en un grado razonable. Entonces, si el hardware cambia, podríamos decidir analizar nuestros algoritmos bajo un modelo diferente de cómputo que sea más apropiado para el nuevo hardware. Así es como el hardware puede afectar el tiempo de ejecución.

La razón por la que esto no es obvio es porque, en las clases introductorias, a menudo no hablamos sobre el modelo de computación. Simplemente hacemos algunas suposiciones implícitamente, sin hacerlas explícitas. Eso es razonable, para fines pedagógicos, pero tiene un costo: oculta este aspecto del análisis. Ahora ya lo sabes.

Creo que hay un malentendido fundamental en la pregunta. Se compara a una persona que encuentra un objeto en una lista ordenada (por ejemplo, una página específica de un libro, dado su número) con una computadora que busca un elemento de una matriz.

$O(\log n)$$O(1)$

Entonces, sí, el hardware (es decir, el modelo de cálculo) afecta el tiempo de ejecución de los algoritmos, como explica DW , pero eso no es en lo que parece estar basado su ejemplo de acceso a matriz.

No, el hardware no afecta la complejidad de los algoritmos.

Pero sí afecta la elección del algoritmo, y puede afectar la utilidad del análisis de complejidad hasta un punto en el que el análisis deja de tener sentido (o simplemente es de interés académico).

Encontrar el cajón correcto (como acceder a un elemento de matriz) usa el algoritmo "abrir el enésimo elemento directamente por índice", no el algoritmo "buscar linealmente" o "hacer búsqueda binaria". Los algoritmos no cambian, sino la elección.

Por otro lado, el análisis de complejidad en sí mismo, o más bien su significado, se ve muy afectado por el hardware.

Muchos algoritmos que son estelares por su análisis de complejidad son de bajo rendimiento o incluso inútiles en la práctica porque el factor constante insignificante no es nada insignificante, sino dominante .

O, porque las suposiciones que alguna vez fueron verdaderas (o mayormente verdaderas) ya no son válidas. Como, por ejemplo, cada operación es casi la misma (solo pequeñas diferencias constantes que no importan), o no hace ninguna diferencia a qué ubicaciones de memoria tiene acceso en qué orden. Mediante el análisis de complejidad, puede concluir que algunos algoritmos son muy superiores porque solo necesitan muchas operaciones. En la práctica, es posible que cada operación provoque una pérdida de caché garantizada (o peor aún, un error de página), que introduce una k que es tan grande que ya no es insignificante, sino que domina todo.
Si el algoritmo A toma 500 operaciones para procesar un conjunto de datos de un tamaño dado y el algoritmo B toma solo 5, pero B causa 5 fallas que queman veinte millones de ciclos cada una, entonces, a pesar de lo que el análisis o el sentido común puedan decirle, A es mejor.

Esto ha llevado a sorpresas divertidas como, por ejemplo, en Cuckoo Hashing hace unos años. Lo cual fue muy superior porque [larga lista de beneficios]. Después de que el bombo se enfrió, resultó que era muy inferior porque garantizaba dos errores de caché (fallas, para conjuntos de datos más grandes) en cada acceso.

Similar ha sucedido con la identificación y el procesamiento de subconjuntos de datos. A menudo, la solución correcta hoy en día es: "hazlo todo" , es decir, en lugar de averiguar lo que necesitas probar y hacer eso, procesa el conjunto de datos completo de forma lineal, incluso si tal vez solo necesitas la mitad. Porque, lo creas o no, eso es más rápido debido a que no hay predicciones erróneas de sucursales, errores de caché ni fallas de página.
¿Necesita leer los primeros 8kB y los últimos 3kB de un archivo de 3MB? Bueno, lea el archivo completo y deseche lo que no quiere, porque buscar en el medio será diez veces más lento que simplemente leerlo completo.

¿Usar un mapa porque tiene complejidad logarítmica? ¿O una tabla hash, que tiene un tiempo de acceso constante? Constante suena increíble. Bueno, para cualquier cosa con menos de mil cosas (dependiendo del hardware, el tamaño de los datos y el patrón de acceso), una búsqueda lineal puede ser igual o mejor. Sorpresa.

Por lo tanto, no son los algoritmos per se los que se ven afectados, sino su utilidad y elección.