Informatiker Board | Druckvorschau: Komplexitätsklasse und Laufzeitkomplexität bestimmen

Geschrieben von Der_Fichtenelch am 04.02.2016 um 15:42:

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.

Geschrieben von eulerscheZahl am 04.02.2016 um 17:31:

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.

Geschrieben von Der_Fichtenelch am 05.02.2016 um 02:17:

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?

Geschrieben von eulerscheZahl am 05.02.2016 um 07:46:

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.