Analisi della complessità temporale del codice

Question

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

    return x;
}

Devo analizzare la sua complessità temporale. Ho notato che raggiunge n molto più velocemente di log(n). Voglio dire, esegue meno passaggi di O(log(n)). Ho letto la risposta ma non ho idea di come ci siano riusciti: è O(log(log(n)). Ora, come affronti una domanda del genere?

Answer 1

Lascia

L3 = accedi alla base 3 L2 = Accedi alla base 2

Quindi la risposta corretta è O (L3 (L2 (n)) e NON O (L2 (L2 (n)).

Inizia con x = x * 2 . x aumenterà esponenzialmente fino a raggiungere n, rendendo così la complessità temporale O (L2 (n))

Ora considera x = x * x . x aumenta più velocemente di quanto sopra. In ogni iterazione il valore di x passa al quadrato del suo valore precedente. Facendo un po 'di matematica semplice, ecco cosa otteniamo:

Per x = 2 n = 4, iterazioni prese = 1 n = 16, iterazioni prese = 2 n = 256, iterazioni prese = 3 n = 65536, iterazioni prese = 4

Pertanto, la complessità temporale è O (L2 (L2 (n)) . Puoi verificarlo mettendo i valori sopra i valori per n.

Ora stai arrivando al tuo problema, x = x * x * x . Ciò aumenterà anche più velocemente di x = x * x. Ecco la tabella:

Per x = 2 n = 8, iterazioni prese = 1 n = 512, iterazioni prese = 2 n = (512 * 512 * 512), iterazioni prese = 3 e così via

Se lo osservi attentamente, questo risulta essere O (L3 (L2 (n)) . L2 (n) ti darà la potenza di due, ma dal momento che stai prendendo il cubo di x in ogni iterazione, dovrai prendere il registro alla base 3 per scoprire il numero corretto di iterazioni prese.

Quindi penso che la risposta corretta sia O(log-to-base-3(log-to-base-2(n))

Generalizzando questo, se x = x * x * x * x * .. (k volte) , la complessità temporale è O (log-to-base-k (log -to-base-2 (n)

Answer 2

pensala come una funzione ricorsiva:

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

se lo espandi:

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

la funzione cresce come la potenza del potere ... quindi il tempo (iterazioni) per raggiungere un certo numero (cioè calcolare l'inverso della funzione) è il logaritmo del logaritmo.

Come nel tuo esempio f(0) = 2, vogliamo sapere quando f(i) >= n è n il parametro di input (e i il numero di iterazioni):

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

Quindi, per raggiungere un valore di takes log_3(log_2(n)), <=> iterazioni (arrotondare mentre si tratta di numeri interi per superarlo).

se la funzione fosse:

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

allora il modello sarebbe:

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

E in questo caso, l'inverso della funzione sarebbe un singolo logaritmo in base 2.

La mia matematica non è molto rigorosa, ma spero che tu abbia l'idea.

Answer 3

Pensa a come x cambia con il numero di iterazioni nel ciclo. Ogni volta, lo cubi. Quindi dopo le iterazioni, il valore sarà di 2 cubi, cubati di nuovo ... e così via, volte. Usiamo x (i) per indicare questa espressione. Diciamo x (0) = 2, x (1) = 2 3, ecc. (Sto usando a b per indicare un elevato alla potenza bth).

Abbiamo finito quando x (i) > = n. Quanto tempo ci vuole? Risolviamo per 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)

Possiamo ignorare i fattori costanti e rimaniamo con la conclusione che prenderemo i passaggi del log (log (n)). Questa è la complessità del tuo algoritmo.

Speriamo che abbattere tutti i passaggi in questo modo aiuti.

Answer 4

Se il codice all'interno del ciclo while fosse

x = 2*x;

x raggiungere n nelle iterazioni O (log (n)). Dato che stai cubando x invece di moltiplicarlo per una costante, raggiungerai n più velocemente.

Answer 5

Dato

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

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

Quanto più veloce o più lenta (misurata dal numero di iterazioni del loop) questa funzione sarà rispetto alla tua funzione?

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 più veloce o più lenta sarà questa funzione rispetto alla tua funzione?

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

Ma questa funzione incrementa log_log_x solo di una costante, quindi è facile capire quante iterazioni fa.

Answer 6

Sia i il numero di passaggi di iterazione e x(i) il valore di x dopo x(i) < n passaggi. Abbiamo

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

Il numero totale di passaggi è il più grande <=>, quindi <=>.

Abbiamo

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

Il logaritmo è in costante aumento, quindi

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

Perché non aggiungere una variabile contatore per contare il numero di iterazioni del ciclo. Stampalo appena prima che la funzione ritorni.

Quindi chiama la funzione per un intervallo di valori, ad es. Da 3 a 1.000.000 per cominciare. Quindi traccia il tuo risultato usando qualcosa come GNUPlot .

Quindi verifica se il grafico corrisponde a una curva nota.