Bestimmung der Komplexität für rekursive Funktionen (Big-O-Notation)

Question

Ich habe morgen eine Zwischenprüfung in Informatik und brauche Hilfe bei der Bestimmung der Komplexität dieser rekursiven Funktionen. Ich weiß, wie man einfache Fälle löst, aber ich versuche immer noch zu lernen, wie man diese schwierigeren Fälle löst. Dies waren nur einige der Beispielprobleme, die ich nicht lösen konnte. Jede Hilfe wäre sehr willkommen und würde mir bei meinen Studien sehr helfen, vielen Dank!

int recursiveFun1(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun1(n-1);
}

int recursiveFun2(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun2(n-5);
}

int recursiveFun3(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun3(n/5);
}

void recursiveFun4(int n, int m, int o)
{
    if (n <= 0)
    {
        printf("%d, %d\n",m, o);
    }
    else
    {
        recursiveFun4(n-1, m+1, o);
        recursiveFun4(n-1, m, o+1);
    }
}

int recursiveFun5(int n)
{
    for (i = 0; i < n; i += 2) {
        // do something
    }

    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun5(n-5);
}

Answer 1

Ich sehe, dass bei der akzeptierten Antwort (recursivefn5) einige Leute Probleme mit der Erklärung haben, also würde ich versuchen, sie nach bestem Wissen und Gewissen zu erklären.

1. Die for-Schleife läuft n/2 mal, weil wir bei jeder Iteration i (den Zähler) um den Faktor 2 erhöhen. Sagen wir also n = 10, dann läuft die for-Schleife 10/2 = 5 mal, d.h. wenn i 0, 2, 4, 6 bzw. 8 ist.

2. In gleicher Weise wird der rekursive Aufruf bei jedem Aufruf um den Faktor 5 reduziert, d.h. er läuft n/5 mal. Nehmen wir erneut an, dass n = 10 ist, so läuft der rekursive Aufruf 10/5 = 2 Mal, d.h. wenn n 10 und 5 ist, und dann trifft er auf den Basisfall und bricht ab.

3. Bei der Berechnung der Gesamtlaufzeit wird die for-Schleife bei jedem Aufruf der rekursiven Funktion n/2 Mal ausgeführt. Da die rekursive Funktion fxn n/5 Mal (in 2 oben) ausgeführt wird, läuft die for-Schleife (n/2) * (n/5) = (n^2)/10 Mal, was zu einer Gesamtlaufzeit von O(n^2) führt - ohne Berücksichtigung der Konstante (1/10)...

Answer 2

Berichtigung und Analyse für recursiveFun3

Meine Korrektur der Problemstellung und die meines Erachtens richtige Analyse sind auf diesem Foto zu sehen.