Was ist die zeitliche Komplexität dieser Funktion?

Dies ist ein Beispiel in meinen Vorlesungsunterlagen. Ist diese Funktion mit zeitlicher Komplexität ? Da der schlimmste Fall ist, geht die Funktion in einen Zweig und 2 verschachtelte Schleifen mit einer zeitlichen Komplexität von und , also ist es . Habe ich recht?$O(n \log n)$else$\log n$$n$$O(n \log n)$

int j = 3;
int k = j * n / 345;
if(k > 100){
    System.out.println("k: " + k);
}else{
    for(int i=1; i<n; i*=2){
        for(int j=0; j<i; j++){
            k++;
        }
    }
}

Die zeitliche Komplexität des genannten Algorithmus ist , da Sie für eine konstante Operation (println) haben und wissen: , bedeutet für Ihr Algorithmus eine konstante Laufzeit hat (auch der andere Teil ist konstant, da nur für aufgerufen wird).$O(1)$$K>100$$j=3,k = 3 \cdot n / 345 \implies 100 = 3\cdot n / 345 \implies n=11500$$n\ge 11500$$n<11500$

Um klarer zu sein, werfen Sie einen Blick auf diese Frage.

EDIT: Wie von Saeed Amiri hervorgehoben, ist dies tatsächlich $O(1)$, da für asymptotisch groß $n$wird der elseZweig nicht wirklich genommen; Das ifTeil wird ausgeführt, was trivial konstant ist. Der Rest dieser Antwort, die ich als Referenz hinterlasse, wäre richtig, wenn zum Beispiel die Bedingung wäre k < 100. Entschuldigung für die Verwechslung.

Die zeitliche Komplexität wird im Wesentlichen in der Größenordnung der Häufigkeit liegen $k$wird in der verschachtelten forSchleife inkrementiert . Es gibt einige zusätzliche Dinge, aber wenn Sie darüber nachdenken, spielt das nur mit konstanten Faktoren. Wie oft wird$k$ erhöht werden?

Wann $i = 1$, $k$wird einmal erhöht. Wann$i = 2$, $k$wird zwei weitere Male erhöht. Wann$i = x$, $k$ wird erhöht $x$zusätzliche Zeiten. Nehmen wir das jetzt an$n = 2^m + 1$. Dann wird die letzte Iteration der inneren Schleife kinkrementiert$2^m$ mal.

$k$ wird eine Gesamtsumme von erhöht $1 + 2 + ... + 2^m$ mal oder $2^{(m+1)} - 1$mal. Erinnern Sie sich daran, dass `$n = 2^m + 1$. Damit$n - 1 = 2^m$und das haben wir $k$ wird erhöht $2(n - 1) - 1$ mal insgesamt.

$k$ wird mehrmals inkrementiert, was linear ist $n$;; Ergo ist das alles$O(n)$.

Obwohl die Kommentare zu den if / else-Zweigen alle korrekt sind, würde ich sagen, dass die Antwort O (log n) ist. Der Grund ist, dass

System.out.println("k: " + k);

beinhaltet die Konvertierung einer Ganzzahl in eine Zeichenfolgenausgabe, und dies ist im allgemeinen Fall O (log n) (nur um jede Ziffer auszudrucken, selbst wenn eine Nachschlagetabelle verwendet wurde).

Ich bin mir nicht sicher, ob das ein Trick war oder nicht ...

Wir werden sehen:

int j = 3; nimmt konstante Zeit O (1).

int k = j * n / 345Nimmt eine Logarithmus-Zeitfunktion von j- und n- Variablen

if (k > 100) nimmt konstante Zeit O (1).

System.out.println("k: " + k);nimmt die Logarithmuszeitfunktion von k

for (int i=1; i<n; i*=2)nimmt die Logarithmuszeitfunktion von n , Θ (log (n)), um genau zu sein, denn wenn t die Anzahl der Iterationen dieser for-Schleife ist, kann der Wert von i ausgedrückt werden als: i = 2 ^t-1 , wenn t = 1 in der ersten Iteration, so dass die Schleife so lange fortgesetzt wird, wie 2 ^t-1 <n ist , wobei sich n nicht ändert.

Wenn im Kalkül 2 ^t-1 <n ist, dann ist t-1 <log ₂ (n)

Und wenn t-1 <log ₂ (n) ist, dann ist t <log ₂ (n) +1

Und wenn in jeder Iteration t um 1 erhöht wird, können wir sehen, dass diese for-Schleife wirklich Θ (log (n)) Zeit benötigt, wenn die Laufzeitkomplexität des Codes in dieser for-Schleife konstant ist, dh O (1) Na sicher!

In dieser for-Schleife befindet sich eine weitere for-Schleife:

for (int j=0; j<i; j++) k++;

Lassen Sie uns dies analysieren:

k++; nimmt konstante Zeit, dh O (1) Zeit.

Daher ist es interessant, die Laufzeitkomplexität der inneren for-Schleife zu analysieren.

Wir werden sehen:

Gemäß dem Code dieser inneren for-Schleife scheint es i Iterationen in dieser inneren for-Schleife zu geben, daher ist die Laufzeit Θ (i) , nicht nur O (i) , da sie in der Mitte nicht bricht. aber denken Sie daran, dass i <n ist , wegen der äußeren for-Schleife, so dass, obwohl am Anfang 1 Iteration erforderlich ist, wenn i = 1 , 2 Iterationen, wenn i = 2 , 4 Iterationen, wenn i = 4 , 8 Iterationen, wenn i = 8 . .. und etc, weil ich mich am Ende der äußeren for-Schleife in der Zeile i * = 2 verdopple , also beträgt die Ausführung insgesamt 1 + 2 + 4 + 8 + ... Iterationen, aber bis i≥nDie maximal mögliche Anzahl von Iterationen in dieser inneren for-Schleife ist also, wenn i = n-1 im schlimmsten Fall. Wenn also in der letzten Ausführung der inneren for-Schleife n-1 Iterationen ausgeführt wurden, bevor sie ausgeführt wurden ( n-1) / 2 Iterationen und davor lief es (n-1) / 4 Iterationen und davor lief es (n-1) / 8 Iterationen ... also war die Ausführung insgesamt:

n-1 + (n-1) / 2 + (n-1) / 4 + (n-1) / 8 ... = (n-1) (1 + 1/2 + 1/4 + 1/8 ...) = (n-1) (2) = 2n-2 = Θ (n)

Denken Sie daran, dass 1 + 1/2 + 1/4 + 1/8 ... = 2 eine bekannte Summe der geometrischen Sequenzen ist.

Denken Sie daran, dass die äußere for-Schleife Θ nimmt (log (n))

Und die innere for-Schleife nimmt Θ (n).

Und die Laufzeitkomplexität der for-Schleife innerhalb der for-Schleife ist die Laufzeitkomplexität der äußeren for-Schleife multipliziert mit der Laufzeitkomplexität der inneren for-Schleife, daher dauert es Θ (nlogn) Laufzeit.

Zusammenfassend ist die Laufzeit dieser Funktion also Θ (nlogn) .

Ich hoffe, dass dies Ihre Frage gut beantwortet und Ihnen zeigt, wie Sie die Laufzeitkomplexität von Algorithmen und Funktionen analysieren können.