javascript - ¿Por qué comparar cadenas 0(n), pero comparar números 0(1)?

computer-science equality

Question

Entiendo que para comparar dos cadenas para la igualdad, el intérprete tiene que recorrer ambas cadenas y comparar cada carácter.

Eso haría que la complejidad del tiempo sea 0(n) donde n es la longitud de la cadena más corta.

Sin embargo, comparar dos números para igualdad es 0(1) .

¿Porqué es eso? ¿No tendría que interpretar el intérprete cada número para verificar la igualdad?

Answer 1

Cuerda

Las comparaciones de cadenas suelen ser una exploración lineal de los caracteres, que devuelve falso en el primer índice donde los caracteres no coinciden.

La complejidad del tiempo es O (N) y el tiempo real que se necesita depende de cuántos caracteres deben escanearse antes de que surjan diferencias estadísticamente. No hay una respuesta simple, pero la respuesta es obvia ;-)

Números

Si dos enteros son iguales, es imposible saberlo sin comparar todos sus bits. Entonces, en caso de igualdad, el tiempo necesario es proporcional al número de bits (que es proporcional al log (abs (N)) si N es uno de los comparables).

Si de hecho no son iguales, hay muchos casos, todos relevantes para la implementación interna. Las entradas largas se almacenan como un vector de "dígitos" en una base de potencia de 2. Si los vectores no tienen las mismas longitudes, entonces las entradas no son iguales, y eso lleva un tiempo constante.

Pero si tienen la misma longitud, entonces los "dígitos" deben compararse hasta encontrar el primer par (si lo hay) que no coinciden. Eso lleva un tiempo proporcional al número de dígitos que deben compararse.

Answer 2

En general, solo usamos la notación big-O cuando n puede elevarse a valores obscenamente grandes, porque la notación big-O describe cómo crece el tiempo de ejecución a medida que crece la entrada. Por ejemplo, al ordenar una lista, la mayoría de los mejores algoritmos se ordenan en O(n log n) , lo que significa, y solo significa, que cuando la lista es lo suficientemente larga, el tiempo que toma ordenarla es proporcional a n log n . Cuando la lista no es lo suficientemente larga, otros factores (por ejemplo, en cualquier momento que su algoritmo pueda tomar para asignar espacio adicional), se vuelven significativos e incluso pueden tomar el tiempo de ejecución.

Con las cadenas de JavaScript, n puede llegar a ser arbitrariamente grande *, por lo que decimos que la comparación lleva O(n) tiempo. Pero con los números de JavaScript (que son números de coma flotante de precisión doble IEEE 754 ), n tiene un límite máximo de 64-1 para un bit de signo, 11 para un exponente y 53 para dígitos significativos **. Debido a esto, sabemos exactamente cuánto tiempo tomará una comparación de números, y los mejores sistemas que tenemos para comparar números de ese tamaño exacto funcionan más o menos independientemente de cuántos de esos 64 dígitos cada número realmente tiene - por lo tanto, comparar estos números en JavaScript se considera O(1) .

* Técnicamente, hay un límite superior porque la memoria RAM puede agotarse. Sin embargo, el lenguaje no especifica un tamaño máximo para las cadenas, y la parte O(n) de la comparación de cadenas domina el tiempo de ejecución mucho antes de que eso suceda.

** Por cierto, esto significa que los números en JavaScript no pueden aumentar infinitamente. Más allá de cierto punto, comienzan a tirar dígitos más pequeños (por ejemplo, los números por encima de 2 ^ 53 solo pueden ser pares, y los números por encima de 2 ^ 54 solo pueden ser divisibles por 4), y cuando el número crece lo suficiente, se redondea hasta el infinito. Por el contrario, si divide un número una y otra vez para hacerlo infinitamente pequeño, eventualmente se redondeará a cero.

Answer 3

Los números en las computadoras generalmente se manejan en unidades de tamaño fijo. Un int puede tener 32 o 64 bits en cualquier combinación de idioma y / o compilador / plataforma, pero nunca será de longitud variable.

Por lo tanto, tiene un número fijo de bits para comparar al comparar números. Es muy fácil construir un circuito de hardware que compare tantos bits a la vez (es decir, como "una acción").

Las cadenas, por otro lado, tienen longitudes inherentemente variables, por lo que solo decir "cadena" no le dice cuántos bits tendrá que comparar.

Sin embargo, hay excepciones, ya que hay números de longitud variable, generalmente llamados algo como BigInteger o BigDecimal que se comportarán de manera muy similar a String comparación de String ya que podría terminar siendo O (n) para comparar dos valores de BigDecimal para la igualdad (donde n es el longitud de BigDecimal s, ninguno de sus valores numéricos).

Answer 4

Por lo general, los programas representan números como estructuras de datos de tamaño fijo (valores binarios, por lo que puede ver sus tamaños descritos en bits). Al ser de tamaño fijo, las comparaciones tomarían una cantidad constante de tiempo y serían O (1), que es uno de los beneficios de dicha representación. Una desventaja sería un límite en el rango de valores que se pueden representar.

Una representación alternativa que levanta esta restricción, permitiendo un rango de números arbitrariamente grande, por lo tanto ya no sería de tamaño fijo, y ya no sería O (1) para comparar.