c++ - rapper - big o notation java

¿Se ha reducido el tiempo de ejecución de esta función de cadena única desde el enfoque ingenuo O(n ^ 2)?

Question

El algoritmo genérico para deducir si una cadena contiene todos los caracteres únicos (y que no utiliza ninguna otra estructura de datos) dice que debe pasar por la cadena, iterando cada letra contra toda la cadena en busca de una coincidencia. Este enfoque es O (n ^ 2) .

El enfoque a continuación (escrito en C) utiliza un desplazamiento para la iteración sobre la parte de la cadena, ya que, por ejemplo, en una cadena corta no hay razón para probar el último carácter con el primer carácter, ya que el primer carácter ya lo hizo.

Mi pregunta es la siguiente: ¿Es el tiempo de ejecución del algoritmo O (n!) O algo así como O (nlogn) ?

#include <stdio.h>

int strunique(const char *str)
{
    size_t offset = 1;
    char *scout = (char *)str, *start;

    for (; *scout != ''/0''; ++scout, ++offset)
        for (start = (char *)str + offset; *start != ''/0''; ++start)
            if (*start == *scout)
                return 0;

    return 1;
}

int main(void)
{
    printf("%d/n", strunique("uniq"));
    printf("%d/n", strunique("repatee"));

    return 0;
}

Answer 1

Respuesta corta

Si el número de caracteres posibles (que no debe confundirse con la longitud de las cadenas ) no es fijo (no es el caso aquí), la complejidad del tiempo de su algoritmo es O (n ^ 2) . Si asumimos que solo hay un número fijo de caracteres válidos (en este caso, 255 / 4G ), su algoritmo se ejecuta en el caso más desfavorable O (n) . Si la condición se mantiene , el algoritmo puede mejorarse fácilmente para ejecutarse en O (1) .

Nota sobre el comportamiento asintótico y big-oh : estos son resultados teóricos . No es porque un algoritmo se ejecuta en O (1) , se ejecuta en un tiempo razonable . Significa que se ejecuta en tiempo constante. Así que, hablando asintóticamente, no hará ninguna diferencia si ingresa una cadena con una longitud de 10 ¹⁰⁰⁰ o una con una longitud de 10 ^10''000 (dado que estas longitudes son lo suficientemente grandes). El tiempo que toma puede ser más de cien veces la edad del universo también.

Explicación

Puede hacer un análisis simple más que en el peor de los casos en los bucles for:

for (; *scout != ''/0''; ++scout, ++offset)
    for (start = (char *)str + offset; *start != ''/0''; ++start)
        //single statement

Ahora queremos saber cuántas veces se repetirá la declaración única (que contiene un número fijo de declaraciones). Ya que nunca modificas el contenido de la cadena. Sabemos que hay un índice n en el que el valor es /0 .

Así que podemos reescribirlo como:

for (scout = 0,offset = 0; scout < n; ++scout, ++offset)
    for (start = offset; *start < n; ++start)
        //single statement

(He asumido que la cadena comienza en la dirección de memoria 0 ), pero como eso es solo un cambio, eso está permitido, hace que sea más simple razonar sobre esto.

Ahora vamos a calcular el número de declaraciones en el bucle interno for (parametrizado). Eso es igual a:

Con o el desplazamiento yn la longitud de la cadena.

Ahora podemos usar esta fórmula para calcular el número de instrucciones en el nivel externo for -loop. Aquí o comienza con 0 e itera hasta (excluyendo) n . Así que el número total de instrucciones es:

Que es O (n ^ 2) .

Pero ahora hay que preguntar: ¿ es posible construir una cadena de este tipo ? La respuesta es no ! Solo hay 255 caracteres válidos (el carácter NUL no se considera un carácter); Si no podemos hacer esta suposición, lo anterior se mantiene. Supongamos que el primer carácter es una a (con un carácter arbitrario), luego o coincide con otra a en la cadena, que puede resolverse en tiempo O (n) (recorrer el resto de la cadena); o significa que todos los demás personajes son diferentes de a . En el primer caso, el algoritmo termina en O (n); en el segundo caso, esto significa que el segundo carácter es diferente.

Digamos que el segundo personaje es b . Luego volvemos a iterar sobre la cadena en O (n) y si encuentra otra b terminamos, después de los pasos 2n o O (n) . Si no es así, debemos tratar de encontrar una coincidencia para el siguiente carácter c .

El punto es que solo necesitamos hacer esto como máximo 255 veces : porque solo hay 255 caracteres válidos . Como resultado, la complejidad del tiempo es 255n o O (n) .

Explicación alternativa

Otra variante de esta explicación es "si el bucle for externo busca el carácter i-th, sabemos que todos los caracteres a la izquierda de i son diferentes de ese carácter (de lo contrario, ya lo habríamos rechazado anteriormente)". Ahora, ya que solo hay 255 caracteres y todos los caracteres de la izquierda son diferentes entre sí y el carácter actual, sabemos que para el 256º carácter de la cadena, ya no podemos encontrar un nuevo carácter diferente, porque no hay tales caracteres. caracteres.

Ejemplo

Digamos que tienes un alfabeto con 3 caracteres ( a , c ) - esto solo para que sea más fácil entender el asunto. Ahora digamos que tenemos una cuerda:

scout
v
b a a a a a b
  ^
  start

Está claro que su algoritmo usará pasos O (n) : el start simplemente iterará una vez en toda la cadena, alcanzará b y volverá.

Ahora digamos que no hay duplicado de b en la cadena. En ese caso, el algoritmo no se detiene después de iterar sobre la cadena una vez. Pero esto implica que todos los demás caracteres deben diferir de a (después de todo, hemos iterado sobre la cadena y no hemos encontrado un duplicado). Así que ahora considera una cadena con esa condición:

scout
v
b a a a a a a
  ^
  start

Ahora está claro que un primer intento de encontrar un carácter b en el resto de la cadena fallará. Ahora su algoritmo incrementa el explorador:

  scout
  v
b a a a a a a
    ^
    start

Y comienza a buscar a . Aquí tenemos mucha suerte: el primer personaje es un a . Pero si hay un duplicado a ; costaría como máximo dos iteraciones, por lo que O (2n) para encontrar el duplicado.

Ahora estamos llegando al caso límite: tampoco hay ninguno. En ese caso, sabemos que la cadena debe comenzar con

    scout
    v
b a c ...

Además, sabemos que el resto de la cadena no puede contener b ''s ni a '' s porque, de lo contrario, el scout nunca se habría movido tan lejos. La única posibilidad restante es que el resto de la cadena contenga c ''s. Así que la cadena dice:

    scout
    v
b a c c c c c c c c c c
      ^
      start

Esto significa que después de iterar sobre la cadena como máximo 3 veces , encontraremos dicho duplicado, independientemente del tamaño de la cadena, o cómo se distribuyen los caracteres entre esa cadena.

Modificar esto a O (1) tiempo

Puede modificar fácilmente este algoritmo para que se ejecute en tiempo O (1): simplemente coloque límites adicionales en los índices:

int strunique(const char *str)
{
    size_t offset = 1;
    char *scout = (char *)str, *start, *stop = scout+255;

    for (; scout < stop && *scout != ''/0''; ++scout, ++offset)
        for (start = (char *)str + offset; start <= stop && *start != ''/0''; ++start)
            if (*start == *scout)
                return 0;

    return 1;
}

En este caso, hemos limitado el primer bucle de manera que visite a lo sumo los primeros 255 caracteres, el bucle interno visita solo los primeros 256 (observe que <= lugar de < ). Por lo tanto, el número total de pasos está limitado por 255 x 256 u O (1) . La explicación anterior ya demuestra por qué esto es suficiente.

Nota : En el caso de que esto sea C , debe reemplazar 255 por 4''294''967''296 lo que en realidad lo hace teóricamente O (n) , pero prácticamente O (n ^ 2) en el sentido de que el factor constante antes de n es tan grande para O (n) que O (n ^ 2) lo superará.

Dado que combinamos la verificación de terminación de cadena con la verificación 256 este algoritmo se ejecutará casi siempre más rápido que el propuesto anteriormente. La única fuente de ciclos potencialmente adicionales es la prueba adicional que se envía con los bucles modificados for . Pero como estos conducen a una terminación más rápida, en muchos casos no resultará en tiempo adicional.

Big-oh

Se puede decir: " Sí, eso es cierto para cadenas con una longitud mayor o igual a 256 caracteres ", "¿Qué pasa con las cadenas con un tamaño inferior a 256 ?". El punto es que el análisis big-oh trata con el comportamiento asintótico . Incluso si el comportamiento fue súper exponencial para algunas cadenas menores o iguales a una cierta longitud, no se tienen en cuenta.

Para enfatizar más el aspecto (problemático) del comportamiento asintótico . Se puede decir que el siguiente algoritmo sería correcto asintóticamente hablando:

int strunique(const char *str) {
    return 0;
}

Siempre devuelve falso; porque "hay una longitud n ₀ tal que para cada longitud de entrada n> n ₀ este algoritmo devolverá el resultado correcto". Esto no tiene mucho que ver con big-oh en sí, es más para ilustrar que uno debe tener cuidado al decir que un algoritmo que se ejecuta en O (1) superará a un algoritmo en O (n ^ 6) para cualquier entrada razonable. A veces el factor constante puede ser gigantesco.

Answer 2

Además de otras respuestas, me gustaría señalar que el problema se puede resolver en O(1) sin memoria adicional y sin modificar el contenido de la cadena de entrada.

Primero, haz strnlen(str, 256) . Si obtienes más de 255, return 0 . Por el principio del casillero, algún carácter debe aparecer más de una vez. Esta operación solo requiere O(1) ya que examinamos solo un prefijo delimitado de la cadena.

Ahora, la cadena es más corta que una constante (256), así que use cualquier algoritmo ingenuo para terminar en solo O(1) tiempo adicional.

Answer 3

No, sigue siendo O (n ^ 2). Acabas de mejorar ligeramente la constante. Aún tiene que hacer dos bucles: básicamente, lo ingenuo cuenta la manera en que los bucles miden el tiempo de O grande, debería decirle esto.

Además, no existe tal cosa como O (n + 1 / 2n). La notación Big O es para darte una idea del orden de magnitud que debe tomar algo. n + 1 / 2n = 1.5n. Dado que la O grande elimina todos los factores constantes, eso sería n.

Sin embargo, puedes vencer a O (n ^ 2) sin memoria adicional. Si nada más puede ordenar las cadenas por valor ascii (tiempo nlog (n)) y luego recorrer la matriz en busca de duplicados (tiempo n) para O (n + nlogn) = tiempo O (nlogn). Probablemente hay otros trucos también.

Tenga en cuenta que el enfoque de clasificación puede no dar un mejor tiempo de ejecución, aunque la forma ingenua tiene un tiempo de ejecución de 1, mientras que el primer algoritmo debe ordenarse, por lo que tiene un mejor caso de nlogn. Así que el mejor momento de la gran O puede no ser la mejor opción.

Answer 4

Su algoritmo es O(N^2) . Esto es muy fácil simplemente al señalar que, en el peor de los casos, una cadena con todos los caracteres únicos, cada carácter debe compararse con cada uno de los caracteres que vienen después. Es decir, en el peor de los casos, N*(N-1)/2 = O(N^2) comparaciones.

Tenga en cuenta que por definición :

f(x) = O(g(x))

si existe alguna constante tal que |f(x)| <= M|g(x)| |f(x)| <= M|g(x)| para todos los suficientemente grandes x . Entonces cuando dices f(x) = O(n + 1/2n) (lo cual es incorrecto para tu algoritmo), eso sigue:

  f(x) = O(n + 1/2n)
  f(x) <= M * (n + 1/2n) for some M, n_0 for n >= n_0, by definition
  f(x) <= (3/2 * M) n, n >= n_0
  f(x) <= M'' n, setting M'' = 3/2 M, n >= n_0
  f(x) = O(n), by definition

Es decir, las constantes siempre se omiten, por lo que es posible que escuche la expresión de que las constantes no importan (al menos en lo que respecta al cálculo de la complejidad del tiempo de ejecución, obviamente son importantes para el rendimiento real)

Answer 5

Una cadena con todos los caracteres únicos puede tener una longitud máxima de 255. En ese caso, su algoritmo se ejecuta en O (1).

Si la cadena contiene caracteres duplicados, uno de esos caracteres duplicados aparece en los primeros 255 elementos de la cadena. Entonces, el peor de los casos es cuando los primeros 254 caracteres de la cadena son únicos y el número 255 se repite hasta el final de la cadena. Entonces su algoritmo se ejecuta en tiempo O (N).

Puede garantizar O (1) tiempo para su algoritmo al verificar primero si la longitud de la cadena es mayor que 255 y fallar inmediatamente si es así.

Todo eso asumiendo que char toma uno de los 256 valores. Si trata el número de caracteres en caracteres como una variable C, las complejidades de su algoritmo son O (C ^ 2) en el caso de que la cadena contenga solo caracteres únicos, O (NC) en el caso de que la cadena contenga duplicados, y puede garantizar el tiempo O (C ^ 2) si primero verifica que la longitud de la cadena no sea mayor que C.

El algoritmo óptimo es O (min (N, C)) al verificar primero que la cadena no sea más larga que C y luego usar cualquier algoritmo de detección de duplicado de tiempo lineal.