Wie würde ich die Zeit und die Raumkomplexität dieses Codes finden?

Question

Ich habe Schwierigkeiten, Platz und Zeitkomplexität für diesen Code zu finden, den ich geschrieben habe, um eine Anzahl von Palindromen in einer Zeichenfolge zu finden.

/**
 This program finds palindromes in a string.
*/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int checkPalin(char *str, int len)
{
    int result = 0, loop;

    for ( loop = 0; loop < len/2; loop++)
    {

        if ( *(str+loop) == *(str+((len - 1) - loop)) )
            result = 1;
        else {
            result = 0;
            break;
        }
    }

    return result;
}

int main()
{
    char *string = "baaab4";
    char *a, *palin;

    int len = strlen(string), index = 0, fwd=0, count=0, LEN;
    LEN = len;

    while(fwd < (LEN-1))
    {
        a = string+fwd;
        palin = (char*)malloc((len+1)*sizeof(char));    

        while(index<len)
        {
            sprintf(palin+index, "%c",*a);
            index++;
            a++;

            if ( index > 1 ) {
                *(palin+index) = '\0';
                count+=checkPalin(palin, index);
            }
        }

        free(palin);
        index = 0;
        fwd++;
        len--;
    }

    printf("Palindromes: %d\n", count);
    return 0;
}

Ich habe es ausgetauscht und das, was ich denke:
Im Main haben wir zwei während der Loops. Die Außenläufe läuft über die gesamte Länge-1 der Saite. Jetzt ist hier die Verwirrung, die innere, während die Schleife zuerst über die gesamte Länge läuft, dann N-1, dann N-2 usw. für jede Iteration der äußeren während der Schleife. Dies bedeutet das auch, dass unsere Zeitkomplexität sein wird O(n(n-1)) = O(n^2-n) = O(n^2)? Und für die Space-Komplexität zuhöre ich anfangs Platz für die Stringlänge+1, dann (Länge+1) -1, (Länge+1) -2 usw. Wie können wir daraus die Raumkomplexität finden? Für die Checkpalin -Funktion ist es O(n/2).
Ich bereite mich auf Interviews vor und möchte dieses Konzept verstehen.
Vielen Dank

Answer 1

Vergessen Sie nicht, dass jeder Anruf zum Checkpalin (das Sie jedes Mal über die innere Schleife von Main ausführen) eine Schleife ausführen index / 2 Zeiten im Inneren Checkpalin. Ihre Berechnung der zeitlichen Komplexität des Algorithmus ist bis auf dieses Problem korrekt. Seit index wird so groß wie n, Dies fügt einen weiteren Faktor von hinzu n zu der Zeit Komplexität, geben Sie o (n)³).

Was die Space Compexity betrifft, zuweisen Sie jedes Mal durch die äußere Schleife, befreien sie aber dann. Die Raumkomplexität ist also O (n). (Beachten Sie, dass o (n) == o (n/2). Es ist nur der Exponent und die Form der Funktion, die wichtig ist.)

Answer 2

Für die Zeitkomplexität ist Ihre Analyse korrekt. Es ist o (n^2) wegen der n+(n-1)+(n-2)+...+1 Schritte. Für die Raumkomplexität zählen Sie im Allgemeinen nur Platz für den benötigten Platz zu einem bestimmten Zeitpunkt. In Ihrem Fall ist das zusätzliche Speicher, den Sie jemals benötigen, O (n) das erste Mal durch die Schleife, sodass die Raumkomplexität linear ist.

Das heißt, dies ist nicht besonders ein guter Code für die Überprüfung eines Palindroms. Sie können es in o (n) Zeit und o (1) Raum tun und haben tatsächlich sauberere und klarere Code zum Booten.

Gah: nicht genau genug gelesen. Die richtige Antwort wird an anderer Stelle gegeben.