Big-O-Analyse mit Funktionen innerhalb von Funktionen

Question

Ich bin verwirrt darüber, wie Big-O funktioniert, wenn man Funktionen innerhalb von Funktionen betrachtet (bei der Analyse des Worst Case). Zum Beispiel, was ist, wenn man so etwas hat:

for(int a = 0; a < n; a++)
{
    *eine Funktion, die in O(n*log(n)) läuft*
    for(int b = 0; b < n; b++)
    {
        *etwas in konstanter Zeit machen*
    }
}

Würde dieser gesamte Block in O(n^2*log(n)) laufen, weil innerhalb der ersten for-Schleife ein O(n) und ein O(n*log(n)) vorhanden sind, also O(n*log(n)) größer ist und daher das ist, was wir nehmen? Oder ist es O(n^3*log(n)), weil du ein O(n) und ein O(n*log(n)) innerhalb der äußeren for-Schleife hast?

Jede Hilfe wird geschätzt! Danke!

Answer 1

Es ist

O(N) * (O(N lg N) + O(N) * O(1)) = O(N) * (O(N lg N) + O(N))
                                 = O(N) * O(N lg N)
                                 = O(N^2 lg N)

Weil du O(N) Durchläufe einer O(N lg N) Funktion und O(N) Konstantzeitoperationen hast. Das O(N lg N) + O(N) vereinfacht sich zu O(N lg N), weil O(N lg N) > O(N) ist.

Answer 2

Bei der Berechnung dieser Art von Komplexität sollten Sie inline oder sequentielle Funktionen hinzufügen und verschachtelte Funktionen multiplizieren.

Zum Beispiel wäre dies O(n):

// O(n) + O(n) = O(2n)` was `O(n)` (da Konstanten entfernt werden)
for (int i = 0; i < n; i++)
{ 
    /* etwas Konstantes */ 
}
for (int j = 0; j < n; j++)
{ 
    /* etwas Konstantes */ 
}

Aber wenn die Funktionen verschachtelt sind, multiplizieren Sie ihre Komplexität:

// O(n) * O(n) = O(n^2)
for (int i = 0; i < n; i++)
{ 
    for (int j = 0; j < n; j++)
    { 
        /* etwas Konstantes */ 
    }
}

Ihr Beispiel ist eine Kombination - Sie haben einige sequentielle Operationen, die in einer anderen Funktion verschachtelt sind.

// das ist O(n*logn) + O(n), was O(n*logn) ist
*eine Funktion, die in O(n*log(n)) läuft*
for(int b = 0; b < n; b++)
{
    *etwas in konstanter Zeit tun*
}

// Multiplikation dieser Komplexität mit O(n)
// O(n) * O(n*logn)
for(int a = 0; a < n; a++)
{
    // deine O(n*logn)
    // deine b-Schleife
}