Algorithmuskomplexität - For-Schleife innerhalb einer While-Schleife; um den Faktor 2 abnehmen

Frage: Wie ist der unten beschriebene Algorithmus "richtig" zu interpretieren?

Ich wollte überprüfen, ob mein Verständnis des folgenden Algorithmus richtig ist, da ich dieses Szenario, bei dem die innere for-Schleife meiner Meinung nach vom Wert von beeinflusst wird, nicht "betroffen" habe M ständig halbiert. Wenn es hilft, laufen Indizes von 1 bis N , und die Eingabe ist ein Integer-Array und eine Größe N .

function F(A[.],n)
    s <- 0
    m <- n
    while m > 0
        for i <- 1 to m do
            s <- s + A[i]
        m <- m/2

Mein Verständnis ist, dass wir uns zuerst die innerste Schleife ansehen, die die for-Schleife ist. Daher ist es drin Ö ( M ) Komplexität, wie es iteriert bis zu M . Außerhalb dieser Schleife befindet sich die While-Schleife, die bei beginnt N aber es halbiert sich ständig, was bedeutet, dass es drin ist Ö ( l Ö G N ) Komplexität. Daher ist die Gesamtkomplexität Ö ( M l Ö G N ) .

Was mich jedoch „stolpert“, ist, weil M halbiert wird, würde dies die innere for-Schleife beeinflussen, was dann bedeuten würde, dass sie das Array "halb" der Zeit durchläuft, also be Ö ( l Ö G N ) Komplexität. Wie zuvor ist die äußere While-Schleife Ö ( l Ö G N ) , daher Gesamtkomplexität ist Ö ( l Ö G N ∗ l Ö G N ) .

Wie soll ich diesen Algorithmus "analysieren", da ich das Gefühl habe, dass die beiden Antworten "brauchbar" sind, aber die untere am "sinnvollsten" ist.

Antworten (1)

HINWEIS

Ihre zusammenfassende Komplexität ist (vorausgesetzt N = 2 P )

∑ k = 1 P ( 3 ⋅ 2 k + 1 )

Können Sie die geometrische Reihe summieren und das Ergebnis umwandeln? N ?

AKTUALISIEREN

Um Ihre Frage in den Kommentaren zu beantworten, besteht jede Iteration der inneren for-Schleife aus 3 Operationen: A[i]Wertsuche s += A[i]und i += 1(Inkrement des Schleifenindex). Ich gehe davon aus +=, dass es atomar ist, dh als eine Operation zählt, wenn Sie in Wirklichkeit Zuweisung und Addition separat implementieren, sind es jeweils 2 Operationen, also insgesamt 5 Operationen.

Schließlich ist eine Iteration der äußeren Schleife m /= 2mit dem check erforderlich m > 0, von dem ich ebenfalls annehme, dass er atomar ist. Wenn nicht, würden Sie hier 3 Operationen benötigen, und die gesamte Schleife wäre 5 ⋅ 2 k + 3 stattdessen.

Hallo gt, danke dafür. Ich frage mich nur, woher kommen diese Werte? (Meine Interpretation ist die 2 k ist der Ö ( l Ö G N ) , Und P ist die obere Grenze der Gleichung, die ist Ö ( l Ö G N ) aber transponiert ist N = 2 P , aber ich bin mir nicht sicher, woher die 3 und +1 kamen). Nochmals vielen Dank für Ihre Hilfe, sehr geschätzt.
@WhatToDisplay hilft gerne weiter, siehe detailliertes Update zur Antwort
Algorithmuskomplexität - For-Schleife innerhalb einer While-Schleife; um den Faktor 2 abnehmen
AntwortenHierDatenschutz-Bestimmungen1y, 0v