Komplexitätsklasse und Laufzeitkomplexität bestimmen

Neue Frage »

Auf diesen Beitrag antworten »
Der_Fichtenelch Komplexitätsklasse und Laufzeitkomplexität bestimmen

Meine Frage:
Hallo zusammen,

ich habe folgenden Codeabschnitt:

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:

public static void main(String[] args) 
    {
        int [] summe = {1,2,3,4,5,6};
        int sum=0;
        
        for (int i=0; i<summe.length;i++)
        {
            sum += summe [i];
        }
        System.out.println(sum);
    }


Meine Ideen:
Bestimmt werden soll die Komplexitätsklasse und die Laufzeitkomplexität. Da der Code eine for-Schleife beinhaltet gehe ich bei der Komplexitätsklasse von O(n) aus. Gibt es eine Änderung der Komplexitätsklasse, wenn ich zum Beispiel nur die ersten 3 Stellen aufaddieren möchte?

Und zur Laufzeitkomplexität? Wie kann ich denn diese berechnen - oder gibt es da nur eine Abschätzung, bzw. ist T(n) dann O(n).


Vielen Dank für die Hilfe.
 
Auf diesen Beitrag antworten »
eulerscheZahl

O(n) ist korrekt.
Wenn du nur die ersten 3 Werte aufaddieren willst, ist das unabhängig von der Eingabelänge, hat also konstante Laufzeit O(1).
Die Komplexitätsklasse ist P (also polynomiell). Ich denke du sollst T(n) gar nicht bestimmen, schau dir aber lieber nochmal an, wie genau die Laufzeitkomplexität bei euch definiert wurde.
Auf diesen Beitrag antworten »
Der_Fichtenelch

Vielen Dank für die Antwort.

Jetzt hätte ich noch den folgenden Code mit der Aufgabenstellung: Analysieren Sie den Zeitaufwand dieser Funktion in Abhängigkeit von dem Parameter n;

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
String numberString(int n) {
String result =””;
int k=0;
for (int i=0; i<n; i++) {
k++;
if (k > 9) k = 0;
result = result + ”,” + k;
}
return result;
}



Wie gehe ich bei solchen "längeren" Codezeilen am Besten vor? Die Zeilen einzeln analysieren und dann am Ende multiplizieren? Hier würde ich auf eine Komplexität von O(n) tippen, zwecks der einzelnen for-Schleife mit n-Durchläufen?
Auf diesen Beitrag antworten »
eulerscheZahl

So gehe ich das auch immer an.

Das Zusammensetzen von Strings ist teuer: es muss jeweils ein komplett neuer String erstellt und der alte Inhalt kopiert werden. Deshalb hängt die Laufzeit hier von der Stringlänge und somit vom n ab.
Insgasamt also O(n^2).

Mehr hier.
 
Auf diesen Beitrag antworten »
Der_Fichtenelch

Vielen Dank.
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »