Análisis de la complejidad del tiempo del código

Question

int foo(int n) 
{
    int x=2;
    while (x<n)
    {
        x = x*x*x;
    }

    return x;
}

Necesito analizar su complejidad temporal. Noté que llega a n mucho más rápido que solo log(n). Quiero decir, hace menos pasos de los que O(log(n)) haría. Leí la respuesta pero no tengo idea de cómo llegaron a ella: es O(log(log(n)). Ahora, ¿cómo abordas esa pregunta?

Answer 1

Let

L3 = inicie sesión en la base 3 L2 = Inicie sesión en la base 2

Entonces la respuesta correcta es O (L3 (L2 (n)) y NO O (L2 (L2 (n)).

Comience con x = x * 2 . x aumentará exponencialmente hasta que alcance n, lo que hace que la complejidad del tiempo sea O (L2 (n))

Ahora considere x = x * x . x aumenta más rápido que el anterior. En cada iteración, el valor de x salta al cuadrado de su valor anterior. Haciendo algunas matemáticas simples, esto es lo que obtenemos:

Para x = 2 n = 4, iteraciones tomadas = 1 n = 16, iteraciones tomadas = 2 n = 256, iteraciones tomadas = 3 n = 65536, iteraciones tomadas = 4

Por lo tanto, la complejidad del tiempo es O (L2 (L2 (n)) . Puede verificar esto poniendo valores por encima de los valores para n.

Ahora abordando su problema, x = x * x * x . Esto aumentará aún más rápido que x = x * x. Aquí está la tabla:

Para x = 2 n = 8, iteraciones tomadas = 1 n = 512, iteraciones tomadas = 2 n = (512 * 512 * 512), iteraciones tomadas = 3 y así sucesivamente

Si miras esto cuidadosamente, resulta ser O (L3 (L2 (n)) . L2 (n) te dará el poder de dos, pero ya que estás tomando el cubo de x en cada iteración, tendrá que llevar el registro a la base 3 para averiguar el número correcto de iteraciones realizadas.

Entonces, creo que la respuesta correcta es O(log-to-base-3(log-to-base-2(n))

Generalizando esto, si x = x * x * x * x * .. (k veces) , entonces la complejidad del tiempo es O (log-to-base-k (log -to-base-2 (n)

Answer 2

piense en ello como una función recursiva:

f(i) = f(i-1)^3

si lo expande:

f(i) = ((f(i-k)^3)^3)[...k times] = f(i-k)^(3^k) = f(0)^(3^i)

la función crece a medida que el poder del poder ... por lo que el tiempo (iteraciones) para alcanzar un cierto número (es decir, calcular el inverso de la función) es el logaritmo del logaritmo.

Como en su ejemplo f(0) = 2, queremos saber cuándo f(i) >= n es n el parámetro de entrada (y i el número de iteraciones):

f(i) = 2^(3^i) >= n
           3^i >= log_2(n)
             i >= log_3(log_2(n))

Por lo tanto, para alcanzar un valor de takes log_3(log_2(n)), se <=> itera (redondea mientras se trata de enteros para superarlo).

si la función sería:

f(i) = 2*f(i-1) //e.g. x=2*x

entonces el patrón sería:

f(i) = 2*2*[...k times]*f(i-k) = f(i-k)*(2^k) = f(0)*(2^i)

Y en este caso, entonces el inverso de la función sería un solo logaritmo en la base 2.

Mis matemáticas no son muy rigurosas, pero espero que entiendas la idea.

Answer 3

Piensa en cómo x cambia con el número de iteraciones a través del ciclo. Cada vez que lo cubres. Entonces, después de i iteraciones, el valor será 2 al cubo, al cubo de nuevo ... y así sucesivamente, i veces. Usemos x (i) para denotar esta expresión. Digamos x (0) = 2, x (1) = 2 3, etc. (estoy usando a b para significar una potencia elevada a la enésima).

Hemos terminado cuando x (i) > = n. ¿Cuánto tiempo se tarda? Resolvamos por i.

First, we take a log on both sides: ln(x(i))>=ln(n)

ln(x(i)) = ln(x(i-1))*3 = ln(x(i-2))*(3**2) = ... = ln(x(0))*(3**i)

(the above uses [this property][1]: ln(x**b)==ln(x)*b)

so, 3**i * 2 >=ln(n). Let's take another logarithm:

ln(3**i * 2) = ln(2) + ln(3)*i 

so ln(2) + ln(3)* i >= ln(ln(n))

Now we can solve for i: i >= ( ln(ln(n))-ln(2) ) / ln(3)

Podemos ignorar los factores constantes, y nos queda la conclusión de que tomaremos los pasos log (log (n)). Esa es la complejidad de su algoritmo.

Con suerte, desglosar todos los pasos de esa manera ayuda.

Answer 4

Si el código dentro del ciclo while fuera

x = 2*x;

x alcanzaría n en O (log (n)) iteraciones. Como estás cubicando x en lugar de simplemente multiplicarlo por una constante, llegarás a n más rápido.

Answer 5

Dado

log ( A * x )     == log ( A ) + log ( x )
log ( x * x * x ) == 3 * log ( x )

Entonces

log ( log ( x * x * x ) ) == log ( 3 * log ( x ) )
                          == log ( 3 ) + log ( log ( x ) )

¿Cuánto más rápido o más lento (medido por el número de iteraciones del bucle) será esta función que su función?

int log_foo ( int n ) 
{
    double          log_x = log ( 2 );
    const double    log_n = log ( n );

    while ( log_x < log_n )
    {
        log_x = 3 * log_x;
    }

    return exp ( log_x );
}

¿Y cuánto más rápido o más lento será esta función que tu función?

int log_log_foo ( int n ) 
{
    double          log_log_x = log ( log ( 2 ) );
    const double    log_log_n = log ( log ( n ) );
    const double    log_3     = log ( 3 );

    while ( log_log_x < log_log_n )
    {
        log_log_x += log_3;
    }

    return exp ( exp ( log_log_x ) );
}

Pero esta función solo incrementa log_log_x en una constante, por lo que es fácil calcular cuántas iteraciones hace.

Answer 6

Sea i el número de pasos de iteración y x(i) el valor de x después de x(i) < n pasos. Tenemos

x(0) = 2
x(i) = x(i-1)³

El número total de pasos es el mayor <=> para que <=>.

Tenemos

log x(i) = log x(i-1)³
         = 3·log x(i-1)
         = 3·log x(i-2)³
         = 3²·log x(i-2)
         = 3^i·log x(0)
         = 3^i·log 2

⇒  log log x(i) = log (3^i·log 2)
                 = log 3^i + log log 2
                 = i·log 3 + log log 2

El logaritmo está aumentando estrictamente, así que

x(i) < n ⇔        log log x(i) < log log n
         ⇔ i·log 3 + log log 2 < log log n
         ⇔                   i < (log log n - log log 2) / log 3 ∈ O(log log n)

Answer 7

¿Por qué no agregar una variable de contador para contar el número de iteraciones del bucle? Imprímalo justo antes de que regrese la función.

Luego llame a la función para un rango de valores, p. 3 a 1,000,000 para empezar. Luego trace su resultado usando algo como GNUPlot .

Luego vea si el gráfico coincide con una curva conocida.