¿Cómo comparamos la complejidad del espacio y el tiempo como O (n ^ 2) tiempo versus O (n) espacio y O (n) tiempo?

Nosotros no?

O estás limitado en el espacio, o en el tiempo, o en ambos, o en ninguno, para un problema en particular. (Perdón por ser muy obvio). Donde tienes limitaciones, tienes que cumplirlas. Ambas restricciones existen normalmente; cómo uno intercambia uno contra el otro (de hecho, si puede hacer esto) se reduce a Otras cosas. No puede “preferir” una solución O (n) en el tiempo a una solución O (n ^ 2) en el tiempo, a pesar de que la primera rompe alguna restricción de espacio y la segunda no. Del mismo modo, pero con más evasión y tejido, con restricciones suaves (el tiempo es a menudo “más suave” que el espacio, pero no siempre; puedes comprar otra computadora) Además, si O (n) en el tiempo es realmente más lento que la solución O (n ^ 2) en el tiempo para el rango real de n que necesita, entonces no se pueden comparar de manera útil. De hecho, si solo necesita un rango limitado específico de n, entonces la notación O es realmente inútil.

No existe una función de preferencia automática universalmente válida sobre, por ejemplo, los números reales que pueden reducir la complejidad del espacio y la complejidad del tiempo a una sola variable libre. Uno puede reemplazar ambas medidas de complejidad con un solo punto que deambula por un espacio de restricción bidimensional, pero ya no se trata de una variable real con sus convenientes relaciones de orden. Alternativamente, puede juntarlos en una sola variable real codificada, y ya no tiene opciones útiles para optimizar usando una función de preferencia. ¡Sin duda, otros enfoques inútiles son posibles! Ninguno de ellos realmente trata el problema básico; Las restricciones de espacio y de tiempo son DIFERENTES, porque el espacio y el tiempo son diferentes en el mundo real. Hasta qué punto son fungibles no es algo que pueda descubrir observando las propiedades de complejidad de un algoritmo.