Laufzeitkomplexität berechnen |
16.05.2015, 22:54 | Auf diesen Beitrag antworten » | |||||
Björn | Laufzeitkomplexität berechnen Meine Frage: Hey Leute, ich stehe momentan echt auf dem Schlauch. Berechnet werden soll die Laufzeitkomplexität T(n) von folgendem Code:
Meine Ideen: Gibt es ein generelles Vorgehen um T(n) zu ermitteln? Vielen Dank für Eure Hilfe :-) |
|||||
|
||||||
17.05.2015, 17:33 | Auf diesen Beitrag antworten » | |||||
eulerscheZahl | Schleifen sind gewöhnlich in O(n) abgearbeitet, bei verschachtelten Schleifen erhöht sich die Potenz jeweils um 1, also O(n^3) für 3 Schleifen. Du musst aber aufpassen, die oft die Schleife durchlaufen wird/ob es eine Abbruchbedingung gibt. Hier hast du O(n). |
|||||
07.09.2015, 19:23 | Auf diesen Beitrag antworten » | |||||
Gast | Falsch! Die Schleife in diesem Fall ist unabhängig vom Parameter "args" (also n). Es kann ein beliebiges Array übergeben werden (der Länge n), die Schleife hat aber immer 10 Schritte, in denen die Summe addiert wird. Es ist somit O(1). |
|||||
07.09.2015, 19:24 | Auf diesen Beitrag antworten » | |||||
Gast | RE: Falsch!
---> bspw. ist im Falle von n = 1000000 dennoch die Schleife 10 Schritte lang (also limitiert, somit O(1)) |
|||||
Anzeige | ||||||
|
||||||
08.09.2015, 14:50 | Auf diesen Beitrag antworten » | |||||
eulerscheZahl | Aber es geht doch nicht um args, sondern um array.length. Wenn man dem array in Zeile 8 noch weitere Werte zuweist, erhöht das linear die Laufzeit. |
|||||
01.02.2016, 10:12 | Auf diesen Beitrag antworten » | |||||
Java_Beginner | Ich steige mal hier mit ein :-) Dass Schleifen eine Komplexität von O(n) haben klingt auf jeden Fall logisch. Doch wie ist es mit O(log n)? Wie genau ist dieses log zu interpretieren? Vielen Dank |
|||||
01.02.2016, 13:17 | Auf diesen Beitrag antworten » | |||||
eulerscheZahl | Beispiel:
Hier wird nicht jeder Wert von i einzeln verwendet, sondern nur sehr wenige. Nämlich log_2(n) viele. Das ist eine Schleife mit logarithmischer Laufzeit. |
|||||
02.02.2016, 09:17 | Auf diesen Beitrag antworten » | |||||
Java_Beginner | Besten Dank, so wird das gleich verständlicher. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |