Komplexitätsklasse und Laufzeitkomplexität bestimmen |
04.02.2016, 15:42 | Auf diesen Beitrag antworten » | |||||
Der_Fichtenelch | Komplexitätsklasse und Laufzeitkomplexität bestimmen Meine Frage: Hallo zusammen, ich habe folgenden Codeabschnitt:
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. |
|||||
|
||||||
04.02.2016, 17:31 | 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. |
|||||
05.02.2016, 02:17 | 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;
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? |
|||||
05.02.2016, 07:46 | 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. |
|||||
Anzeige | ||||||
|
||||||
07.02.2016, 12:11 | Auf diesen Beitrag antworten » | |||||
Der_Fichtenelch | Vielen Dank. |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
|
Die Neuesten » |
|