Técnicamente sí, porque:
- Hay algoritmos de clasificación especializados que se ejecutan en O (n)
- Big-Oh solo denota un límite superior
Dicho esto, para cualquier algoritmo secuencial (independientemente de si ordena o hace algo completamente diferente) la complejidad del espacio es como máximo igual a la complejidad del tiempo, porque en los pasos x el programa solo puede acceder a las celdas de memoria O (x). Por lo tanto, cualquier cosa que se ejecute en tiempo O (n) solo puede usar memoria O (n).
(Nota al pie: hay modelos de cómputo donde la afirmación anterior no es cierta. En estos modelos, uno puede asignar rápidamente grandes fragmentos de memoria que no se han inicializado a ningún valor específico. Si cuenta toda la memoria asignada como se usa, en estos modelos un programa puede usar más espacio que tiempo. Gracias a Igor Markov por señalar esto en la discusión. Lea nuestros comentarios y / o comentarios si desea saber más sobre esto).
- ¿Es una persona inteligente debido a los 'algoritmos' que usa su cerebro? Si es así, ¿alguien podría copiar ese 'algoritmo' para ser igualmente inteligente?
- ¿Cuál es la forma correcta de leer CLRS (Introducción a los algoritmos)?
- Matrices de sufijos: Dadas dos cadenas s1 y s2. ¿Cuál es el mejor algoritmo para encontrar el número de subcadenas comunes entre s1 y s2 de longitud 1, 2,… hasta min (| s1 |, | s2 |)?
- ¿Qué representación gráfica es mejor para la programación competitiva en C ++: lista de adyacencia o matriz de adyacencia?
- ¿Qué es la estructura de datos inmutable?
