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).
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.
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?
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).
