Zeitkomplexität bestimmen

19.06.2023, 21:00	Justinoderso	Auf diesen Beitrag antworten »
Zeitkomplexität bestimmen Meine Frage: Es geht um die Frage, bestimme die O-Notation für den folgenden Code-Block: for i in range ( n ): for j in range ( n ^2) : for k in range ( i j ) : do_something (i , j , k ) # Funktion ist O(1) Meine Ideen:* Meine Überlegung ist O(n^9), die erste Schleife wird ja einfach n mal durch laufen, die zweite n^2 mal. Die dritte wird ij mal durchlaufen. ij beginnt mit 0 und hat ihr Maximum bei n-1n^2-1. Im weiteren werde ich die -1 vernachlässigen, da sie für die Frage nach der O-Notation keine Rolle spielt. nach der Gaußschen Summenformel müsste die Summe von 0 bis n^2n=n^3 ja (n^6+n^3)/2 sein. Alles in summe würde dann nn^2n^6=n^9 ergeben. Oder sehe ich das falsch?
20.06.2023, 09:46	IfindU	Auf diesen Beitrag antworten »
RE: Zeitkomplexität bestimmen Ich glaube du multiplizierst da zu viel. Man kann direkt ablesen, dass die Funktion "do_something" genau $\begin{eqnarray} \sum_{i=1}^{n} \sum_{j=1}^{n^2} \sum_{k=1}^{ ij}1 \end{eqnarray}$ mal aufgerufen wird. Das kann man jetzt rein algebraisch vereinfachen.
20.06.2023, 15:41	Justinimmernoch	Auf diesen Beitrag antworten »
RE: Zeitkomplexität bestimmen Hmm, ich verstehe nicht wie dein Ergbenis anders ist als meins. Kannst du das denn mal für mich vereinfachen?
20.06.2023, 15:50	IfindU	Auf diesen Beitrag antworten »
RE: Zeitkomplexität bestimmen $\begin{eqnarray} \sum_{i=1}^{n} \sum_{j=1}^{n^2} \sum_{k=1}^{ ij}1 = \sum_{i=1}^{n} \sum_{j=1}^{n^2} ij = \left(\sum_{i=1}^{n}i \right)\left( \sum_{j=1}^{n^2} j\right) = \frac 1 4 \left(n(n-1) \right)(n^2(n^2-1)) \leq n^6 \end{eqnarray}$ Edit: Siehe HALs Anmerkung unten für die korrekte Gaußsche Summenformel. Ich schiebe es mal auf die Temperatur in meiner Wohnung
20.06.2023, 16:14	HAL 9000	Auf diesen Beitrag antworten »
$\begin{eqnarray} \left(\sum_{i=1}^{n}i \right)\left( \sum_{j=1}^{n^2} j\right) = \frac 1 4 \left(n(n{\color{red}+}1) \right)(n^2(n^2{\color{red}+}1)) \end{eqnarray}$ Ändert natürlich nichts an der Gesamtabschätzung.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »