Tempo análise de complexidade de código

Question

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

    return x;
}

Eu preciso analisar sua complexidade de tempo. Notei que ele atinja n muito mais rápido do que apenas log(n). Quero dizer, ele faz menos etapas do que O(log(n)) faria. Eu li a resposta, mas não têm idéia de como eles chegaram a ele: É O(log(log(n)). Agora, como você aborda essa pergunta?

Answer 1

Let

L3 = log da base 3 L2 = log da base 2

Em seguida, a resposta correta é O (L3 (L2 (n)) e não com O (L2 (L2 (n)).

Comece com x = x * 2 . x vai aumentar exponencialmente até atingir N, tornando assim a complexidade O (L2 (n))

Agora, considere x = x * x . x aumenta mais rapidamente do que o acima. Em cada iteração o valor de x salta para o quadrado de seu valor anterior. Fazendo uma matemática simples, aqui é o que temos:

Para x = 2 n = 4, iterações feita = 1 n = 16, iterações feita = 2 n = 256, tomada iterações = 3 n = 65536, iterações feita = 4

Assim, a complexidade de tempo é O (L2 (L2 (n)) . Pode verificar isso colocando valores acima de valores para n.

Agora, chegando ao seu problema, x = x * x * x . Isto irá aumentar ainda mais rápido do que x = x * x. Aqui está a tabela:

Para x = 2 n = 8, iterações feita = 1 n = 512, tomada iterações = 2 N = (512 * 512 * 512), feita iterações = 3 e assim por diante

Se você olhar para isso com cuidado, este acaba por ser O (L3 (L2 (n)) . L2 (n) você vai ter a potência de dois, mas desde que você está tomando cubo de x em cada iteração, você terá que tomar log à base 3 do mesmo para descobrir o número correto de iteração tomadas.

Então eu acho que a resposta correta é O (log-to-base-3 (log-to-base-2 (n))

Generalizando este, se x = x * x * x * x * .. (k vezes) , em seguida, a complexidade de tempo é O (log-a-base-k (log -to-base 2 (n)

Answer 2

pensar nisso como uma função recursiva:

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

Se você expandi-lo:

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

a função cresce à medida que o poder do poder ... assim o tempo (iterações) para alcançar um determinado número (isto é, calculando o inverso da função) é o logaritmo do logaritmo.

Como no seu exemplo f(0) = 2, queremos saber quando f(i) >= n sendo n o parâmetro de entrada (e i o número de iterações):

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

Assim, para chegar a um valor de n, ele takes log_3(log_2(n)) iterações (até rodada ao lidar com números inteiros para ultrapassá-lo).

Se a função seria:

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

então o padrão seria:

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

E, neste caso, em seguida, o inverso da função seria uma única logaritmo na base 2.

A minha matemática não é muito rigoroso, mas eu espero que você começa a idéia.

Answer 3

Pense em como x muda com o número de iterações através do laço. Cada vez, você cubo-lo. Então, depois de iterações i, o valor será de 2 em cubos, cubos de novo ... e assim por diante, vezes eu. Vamos uso x (i) para denotar essa expressão. Digamos x (0) = 2, x (1) = 2 3, etc (estou usando um b significar um elevado à potência bth).

Estamos a fazer quando x (i)> = n. Quanto tempo leva? Vamos resolver para 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)

Nós podemos ignorar os fatores constantes, e ficamos com a conclusão de que vamos dar log (log (n)) passos. Essa é a complexidade do algoritmo.

Felizmente, quebrar todos os passos como isso ajuda.

Answer 4

Se o código dentro do loop while foram

x = 2*x;

x n atingiria em O (log (n)) iterações. Desde que você está cubing x em vez de apenas multiplicação por uma constante, você vai chegar n mais rápido.

Answer 5

Dada

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

Assim

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

Quanto mais rápido ou mais lento (medida pelo número de iterações do loop) irá esta função seja do que a sua função?

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 );
}

E quanto mais rápido ou mais lento vai esta função seja do que a sua função?

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 ) );
}

Mas esta função apenas incrementos log_log_x por uma constante, por isso é fácil de trabalhar para fora como muitas iterações ele faz.

Answer 6

Let i ser o número de iteração passos e x(i) o valor de x após as etapas i. Temos

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

O número total de passos é a maior i para que x(i) < n.

Temos

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

O logaritmo é estritamente crescente, então

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 que não adicionar uma variável de contador para contar o número de iterações do loop. Imprimi-lo pouco antes de a função retorna.

Em seguida, chamar a função de uma gama de valores, por exemplo 3 a 1.000.000 para começar. Em seguida, traçar o seu resultado usando algo como GNUPlot .

Em seguida, ver se o gráfico corresponde a uma curva conhecida.