Zeitkomplexität Analyse von Code

Question

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

    return x;
}

Ich brauche seine Zeit, Komplexität zu analysieren. Ich bemerkte es erreicht n viel schneller als nur log(n). Ich meine, tut es weniger Schritte als O(log(n)) tun würde. Ich lese die Antwort, aber haben keine Ahnung, wie sie es bekommen: Es O(log(log(n)) ist. Nun, wie nähern Sie sich eine solche Frage?

Answer 1

Let

L3 = an der Basis log 3 L2 = log zur Basis 2

Dann ist die richtige Antwort auf O (L3 (L2 (n)) und NICHT O (L2 (L2 (n)).

Starten Sie mit x = x * 2 . x steigt exponentiell, bis es n erreicht, so dass die Zeitkomplexität O machen (L2 (n))

Nun betrachten x = x * x . x steigt schneller als die oben. In jeder Iteration springt der Wert von x zum Quadrat seines vorherigen Wertes. einige einfache mathematische tun, hier ist das, was wir bekommen:

Für x = 2 n = 4 ist, genommen Iterationen = 1 n = 16, genommen Iterationen = 2 n = 256, genommen Iterationen = 3 n = 65536, Iterationen genommen = 4

Somit ist die Zeitkomplexität ist O (L2 (L2 (n)) . Sie können dies überprüfen, indem Werte über Werte für n setzen.

Sie jetzt zum Problem kommen, x = x * x * x . Dadurch erhöht sich sogar noch schneller als x = x * x. Hier ist die Tabelle:

Für x = 2 n = 8, genommen Iterationen = 1 n = 512, aufgenommen Iterationen = 2 n = (512 * 512 * 512), aufgenommene Iterationen = 3 und so weiter

Wenn Sie diese sorgfältig prüfen, diese stellt sich heraus, sein O (L3 (L2 (n)) . L2 (n) werden Sie die Leistung von zwei bekommen, aber da Sie nehmen Würfel in jeder Iteration von x, werden Sie auf die Basis 3 davon nehmen müssen sich anmelden, die richtige Anzahl der Iteration genommen, um herauszufinden.

Also ich denke, die richtige Antwort ist O (log-to-Base-3 (log-to-Base-2 (n))

Diese Verallgemeinerung, wenn x = x * x * x * x * .. (k-mal) , dann ist die Zeitkomplexität ist O (log-to-Base-k (log -zu-base-2 (n)

Answer 2

Betrachten Sie es als eine rekursive Funktion:

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

Wenn Sie erweitern es:

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

die Funktion wächst als die Macht der Macht ... so die Zeit (Iterationen) eine bestimmte Anzahl zu erreichen (das heißt, die Umkehrung der Funktion Berechnung) ist der Logarithmus des Logarithmus.

Wie in Ihrem Beispiel f(0) = 2, möchten wir wissen, wann f(i) >= n n der Eingangsparameter ist (und i die Anzahl der Iterationen):

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

So einen Wert von n zu erreichen, ist es Iterationen takes log_3(log_2(n)) (aufrunden, während sie mit ganzen Zahlen zu tun, es zu übertreffen).

, wenn die Funktion sei:

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

dann wäre das Muster sein:

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

Und in diesem Fall dann die Umkehrung der Funktion ein einzelner Logarithmus in Basis wäre 2.

Meine Mathe ist nicht sehr streng, aber ich hoffe, dass Sie die Idee.

Answer 3

Denken Sie darüber nach, wie x ändert sich mit der Anzahl der Iterationen durch die Schleife. Jedes Mal, Würfel Sie es. So, nachdem ich Iterationen wird der Wert 2 in Würfel geschnitten sein, wieder in Würfel geschnitten ... und so weiter, ich mal. Lassen Sie uns verwenden x (i) diesen Ausdruck zu bezeichnen. Lassen Sie uns sagen, x (0) = 2, x (1) = 2 3 usw. (ich bin mit einem b bedeuten, dass ein auf die bth potenziert).

Wir sind fertig, wenn x (i)> = n. Wie lange dauert es? Lassen Sie sich für i lösen.

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)

Wir können die konstanten Faktoren ignorieren, und wir sind mit dem Abschluss verlassen, dass wir log giewen (log (n)) Schritte. Das ist die Komplexität des Algorithmus.

Wir hoffen, brechen alle Schritte wie das hilft.

Answer 4

Wenn der Code innerhalb der while-Schleife war

x = 2*x;

x erreichen würde n in O (log (n)) Iterationen. Da Sie x sind cubing statt nur durch einen konstanten Multiplikation, werden Sie erreichen n schneller.

Answer 5

Da

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

So

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

Wie viel schneller oder langsamer (gemessen nach der Anzahl der Iterationen der Schleife) wird diese Funktion als Ihre Funktion?

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

Und wie viel schneller oder langsamer wird diese Funktion als Ihre Funktion?

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

Aber diese Funktion nur erhöht log_log_x durch eine Konstante, so ist es einfach, herauszufinden, wie viele Iterationen es funktioniert.

Answer 6

Lassen Sie i die Anzahl der Iterationsschritte sein und den Wert von x(i) nach x Schritte i. Wir haben

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

Die Gesamtzahl der Schritte ist der größte i so dass x(i) < n.

Wir haben

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

Der Logarithmus ist streng monoton wachsend, so

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

Warum nicht noch ein Zähler Variable die Anzahl der Iterationen der Schleife zu zählen. Drucken Sie es aus, kurz bevor die Funktion zurückkehrt.

Dann rufen Sie die Funktion für einen Bereich von Werten, z.B. 3 bis 1.000.000 zu beginnen. plotten dann Ihr Ergebnis mit so etwas wie GNUPlot .

Dann sehen, ob die Kurve, die eine bekannte Kurve entspricht.