O-Notation & while-Schleife < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:05 Mo 26.09.2005 | | Autor: | Jacek |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt
Hallo Leute,
ich bedanke mich für die zuletzt gut beantwortete Frage zu Hashfunktionen!
Könntet ihr mir noch mal helfen?
Ist eigentlich nicht allzu schwer:
for( i=0; i < x; i++ )
for( j=i; j < x; j++ );
Wie oft wird das durchlaufen. Ich weiß nur, dass es O(x²) ist.
Aber die einzelnen durchläufe, damit habe ich Probleme.
Und noch bitte etwas:
Wie ist eine while Schleife durch eine do-while Schleife auszugrücken?
Ich hoffe noch einmal auf Eure Hilfe.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:58 Mo 26.09.2005 | | Autor: | bazzzty |
> Ist eigentlich nicht allzu schwer:
>
> for( i=0; i < x; i++ )
> for( j=i; j < x; j++ );
>
> Wie oft wird das durchlaufen. Ich weiß nur, dass es O(x²)
> ist.
Für die nächsten Male: Es wird immer gern gesehen, wenn nicht nur die Aufgabe, sondern auch schon eigene Gedanken dastehen. Dann ist erstens klarer, wo das Problem ist, und zweitens kommt der Verdacht nicht so leicht auf, daß da bloß jemand zu faul zu Nachdenken ist.
> Aber die einzelnen durchläufe, damit habe ich Probleme.
Okay, dann summieren wir doch mal auf: Für [mm]i=0[/mm] wird die innere Schleife [mm]x[/mm] mal durchlaufen, für [mm]i=1[/mm] [mm]x-1[/mm] mal usw. bis [mm]i=x-1[/mm], wo die innere Schleife nur einmal durchlaufen wird. Insgesamt ist die Anzahl der Durchläufe also
[mm]\sum_{i=0}^{x-1} x-i = \sum_{i^\prime=1}^{i^\prime=x} i^\prime = \dots[/mm]
Wenn die Umformung unklar ist, mach Dir klar, welche Zahlen durchlaufen werden, ersetzt wurde [mm]i^\prime = x-i[/mm]. Die geschlossene Form fällt Dir vielleicht selbst ein (Gauß).
> Und noch bitte etwas:
> Wie ist eine while Schleife durch eine do-while Schleife
> auszugrücken?
Dazu vor allem die Frage:
Warum ist
while (Bedingung) {
statement;
}
nicht dasselbe wie
do {
statement;
} while (Bedingung)
In welchem Fall passiert etwas anderes? Wie läßt sich das verhindern?
Ich helfe gerne weiter, aber ich will auch nicht alles auf einmal verraten.
Gruß
Bastian
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:31 Mo 26.09.2005 | | Autor: | Jacek |
Mir ist schon klar, dass bei einer do-while-Schleife zumindest ein Mal der Block durchlaufen wird im Gegensatz zur einfachen while-Schleife...
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:20 Di 27.09.2005 | | Autor: | bazzzty |
> Mir ist schon klar, dass bei einer do-while-Schleife
> zumindest ein Mal der Block durchlaufen wird im Gegensatz
> zur einfachen while-Schleife...
Okay. Um also eine while-Schleife durch eine do/while-Schleife zu ersetzen, muß man, sofern man nicht sicher ist, daß die Bedingung zu Beginn immer erfüllt ist, ggf. die erste Ausführung des Rumpfes / der ganzen Schleife verhindern. Das geht nur mit einem zusätzlichen 'if', wenn ich das richtig sehe:
if (condition)
do {
statement;
} while (condition)
oder
do {
if (condition) statement;
} while (condition)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:43 Di 27.09.2005 | | Autor: | Karl_Pech |
Hallo bazzzty,
> if (condition)
> do {
> statement;
> } while (condition)
Also, ich persönlich bevorzuge eher dieses Konstrukt, weil bei dem Anderen ja jedesmal dieselbe Bedingung doppelt abgefragt wird. Gut, aber das ist Ansichtssache. 
Viele Grüße
Karl
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:40 Di 27.09.2005 | | Autor: | bazzzty |
> > if (condition)
> > do {
> > statement;
> > } while (condition)
>
> Also, ich persönlich bevorzuge eher dieses Konstrukt, weil
> bei dem Anderen ja jedesmal dieselbe Bedingung doppelt
> abgefragt wird. Gut, aber das ist Ansichtssache.
Da bin ich ganz Deiner Meinung, das entspricht mit Deiner Begründung auch präziser der while-Schleife.
|
|
|
| |
|
Hallo Jacek,
> Könntet ihr mir noch mal helfen?
> Ist eigentlich nicht allzu schwer:
>
> for( i=0; i < x; i++ )
> for( j=i; j < x; j++ );
>
> Wie oft wird das durchlaufen. Ich weiß nur, dass es O(x²)
> ist.
> Aber die einzelnen durchläufe, damit habe ich Probleme.
Die verschachtelten Schleifen oben kann man direkt als verschachtelte Summe aufschreiben:
[mm] $\sum_{i=0}^{x-1}{\sum_{j=i}^{x-1}{1}} [/mm] = [mm] \sum_{i=0}^{x-1}{\sum_{j=1}^{x-i}{1}} [/mm] = [mm] \sum_{i=0}^{x-1}{\left(x-i\right)} [/mm] = [mm] \left(\sum_{i=0}^{x-1}{x}\right)-\left(\sum_{i=0}^{x-1}{i}\right) [/mm] = [mm] x^2 [/mm] - [mm] \frac{\left(x-1\right)x}{2} [/mm] = [mm] \frac{x^2}{2} [/mm] + [mm] \frac{x}{2} [/mm] = [mm] \frac{x\left(x+1\right)}{2} \in \mathcal{O}\left(x^2\right)$.
[/mm]
Viele Grüße
Karl
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:11 Mo 26.09.2005 | | Autor: | Italo |
Hmmm,
gehe ich recht in der Annahme, dass die zweite for-Schleife ein Mal weniger durchlaufen wird als die erste?!
Denn beim ersten Eintritt in die for-Schleifen ist ja j gleich 1, denn x wird ja auf eins gesetzt, oder?!
Ist in der Bezeichnung "innere Schleife" die zweite for-Schleife gemeint?
Bitte ebenfalls um Hilfe
|
|
|
| |
|
Hallo Italo,
Ich kopiere den Code-Schnippsel der Übersicht wegen nochmal rein:
| 1: |
| | 2: | for( i=0; i < x; i++ )
| | 3: | for( j=i; j < x; j++ );
|
> gehe ich recht in der Annahme, dass die zweite
> for-Schleife ein Mal weniger durchlaufen wird als die
> erste?!
Das sehe ich nicht so. Vielmehr ist doch die zweite Schleife abhängig von der Ersten. Wenn $i = 0$ ist, ist doch auch $j = 0$, und die zweite Schleife wird somit genau $x$ mal aufgerufen [mm] $\left(0,\dotsc,x-1\text{ mal}\right)$. [/mm] Das geht dann immer so weiter; $i = 1: j = 1 [mm] \Rightarrow [/mm] x-1 [mm] \text{ Aufrufe u.s.w.}$
[/mm]
> Denn beim ersten Eintritt in die for-Schleifen ist ja j
> gleich 1,
Beim ersten Aufruf der inneren Schleife ist doch $i = 0$, also auch $j = 0$.
> denn x wird ja auf eins gesetzt, oder?!
Das verstehe ich nicht. Im Code oben wird doch nirgendwo etwas an das $x$ zugewiesen? Bei dieser Abschätzung geht es alleine um die Laufindizes (also Laufvariablen). Der Schleifenkörper der inneren Schleife ist leer.
> Ist in der Bezeichnung "innere Schleife" die zweite
> for-Schleife gemeint?
Ja, das meinte ich.
Grüße
Karl
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 01:26 Di 27.09.2005 | | Autor: | Italo |
Gut,danke erst Mal für die Hilfe.
Ich meinte, dass durch das Inkrement (i++) nach dem ersten Durchlauf eins ist. Gut?
Da wir dann in die innere Schleife gehen und j=i ist, müsste doch j jetzt 1 sein. Nach dem ersten Durchlauf.
Somit käme ich bei der ersten Schleife auf 0,1,2,..x-1 wie Du/Ihr, jedoch bei der inneren Schleife auf 1,2,3,...,x-2.
Ist das ein Denkfehler, dass ich das erhöhte i aus der aüßeren Schleife sofort auf die innere Schleife ausüben lasse?!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:25 Di 27.09.2005 | | Autor: | bazzzty |
> Gut,danke erst Mal für die Hilfe.
> Ich meinte, dass durch das Inkrement (i++) nach dem ersten
> Durchlauf eins ist. Gut?
Die erste Schleife ist aber erst einmal durchgelaufen, wenn die zweite Schleife einmal von 0 bis x-1 lief.
> Da wir dann in die innere Schleife gehen und j=i ist,
> müsste doch j jetzt 1 sein.
Ich glaube, Du kennst das for-Konstrukt nicht wie verwendet.
Wenn da steht:
for (i = 0; i<x; i++)
statement;
heißt das soviel wie
i=0;
while (i<x) {
statement;
i++;
}
Das Inkrement wird also *nach* dem Schleifenrumpf ausgeführt.
Das ist übrigens, um einen zweiten Fehler vorwegzunehmen, unabhängig davon, ob ich i++ oder ++i schreibe, weil der Ausdruck tatsächlich erst hinter dem Rumpf ausgewertet wird.
Setzt man nun als statement die innere Schleife an, sieht man, daß beim ersten Durchlauf der inneren Schleife i noch 0 ist.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:46 Di 27.09.2005 | | Autor: | Italo |
Gut, ist einleuchtend.
Aber
for( i=0; i < x; i++ );
for( j=0; j < x; j++);
macht 2 mal x durchläufe. Also O(x).
Worin besteht denn hier der Unterschied zu:
for( i=0; i < x; i++ )
for( j=i; j < x; j++ );
Was ja O(x²) ist.????
|
|
|
| |
|
Hallo Italo,
> for( i=0; i < x; i++ );
> for( j=0; j < x; j++);
bazzzty hat vollkommen Recht. Das liegt natürlich in [mm] $\mathcal{O}\left(x\right)$, [/mm] da [mm] $\sum_{i=0}^{x-1}{1}+\sum_{j=0}^{x-1}{1} [/mm] = 2x [mm] \in \mathcal{O}\left(x\right)$ [/mm] ist. Wegen [mm] $\mathcal{O}\left(x\right) \subset \mathcal{O}\left(x^2\right)$ [/mm] ist also die Ausführung der anderen beiden verschachtelten Schleifen asymptotisch langsamer.
Folgendes wäre eine richtige Antwort für die folgenden FOR-Schleifen:
> for( i=0; i < x; i++ ) //;
> for( j=0; j < x; j++);
Auch diese verschachtelten Schleifen kann man sich als verschachtelte Summe aufschreiben:
[mm] $\sum_{i=0}^{x-1}{\sum_{j=0}^{x-1}{1}} [/mm] = [mm] \sum_{i=0}^{x-1}{x} [/mm] = [mm] x^2 \in \mathcal{O}\left(x^2\right)$
[/mm]
> macht 2 mal x durchläufe. Also O(x).
Das stimmt nicht. Das obige Code-Schnippsel läge in [mm] $\mathcal{O}\left(x^2\right)$.
[/mm]
> Worin besteht denn hier der Unterschied zu:
>
> for( i=0; i < x; i++ )
> for( j=i; j < x; j++ );
>
> Was ja O(x²) ist.????
Aus der Sicht der Bachmannschen [mm] $\mathcal{O}-\text{Notation}$ [/mm] werden beide Code-Schnippsel gleich schnell ausgeführt. Sie haben die gleiche Laufzeitkomplexität. [mm] $\mathcal{O}\left(x^2\right)$ [/mm] ist nämlich eine sogenannte Komplexitätsklasse. Es ist quasi eine Menge aller Funktionen, die sich unter einer bestimmten Schranke befinden:
[mm] $f\left(x\right) \in \mathcal{O}\left(g\left(x\right)\right) :\gdw \exists [/mm] c [mm] \in \IR_{>0}\exists x_0 \in \IN \forall [/mm] x [mm] \ge x_0 [/mm] : [mm] \left|f\left(x\right)\right| \le c\left|g\left(x\right)\right|$
[/mm]
Man könnte also genauso korrekt sagen, daß sich die obigen Code-Schnippsel angesichts ihrer Laufzeitkomplexität in [mm] $\mathcal{O}\left(x^3\right)$ [/mm] oder z.B. in [mm] $\mathcal{O}\left(2^x\right)$ [/mm] befinden, da [mm] $\mathcal{O}\left(x^2\right) \subset \mathcal{O}\left(x^3\right) \subset \mathcal{O}\left(2^x\right)$ [/mm] gilt.
Grüße
Karl
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:38 Di 27.09.2005 | | Autor: | bazzzty |
> > for( i=0; i < x; i++ );
> > for( j=0; j < x; j++);
>
>
> Auch diese verschachtelten Schleifen kann man sich als
> verschachtelte Summe aufschreiben:
Auch wenn die Einrückung das suggeriert; die beiden Schleifen sind syntaktisch nicht voneinander abhängig, werden nacheinander ausgeführt.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:42 Di 27.09.2005 | | Autor: | Karl_Pech |
Hallo bazzzty,
Ich editiere meine Antwort jetzt ein Bißchen. Sie ist ja im Grunde nicht falsch, sondern basiert auf zu ungenauem Lesen.
Grüße
Karl
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:36 Di 27.09.2005 | | Autor: | bazzzty |
> for( i=0; i < x; i++ );
> for( j=0; j < x; j++);
> macht 2 mal x durchläufe. Also O(x).
> Worin besteht denn hier der Unterschied zu:
>
> for( i=0; i < x; i++ )
> for( j=i; j < x; j++ );
>
> Was ja O(x²) ist.????
Eine For-Schleife in Java/C ist von der Form
for (Initialisierung; Bedingung; Befehl am Ende des Rumpfes;)
Rumpf
Wobei a) Einrückungen/Zeilenumbrüche/Leerzeichen keinerlei Rolle spielen, und b) der Rumpf wiederum ein beliebiger Befehl (kann auch zusammengesetzt sein) ist.
Was ist ein solcher Befehl oder zusammengesetzter Befehl?
Möglich sind unter anderem
{
....
}
oder
x=1;
oder eine For-Schleife, oder eben auch das leere Statement ';'.
Wenn Du nun schreibst
> for( i=0; i < x; i++ );
> for( j=0; j < x; j++);
Dann steht da überkorrekt:
for (i=0; i<x;i++) {
;
}
for (j=0; j<x;j++) {
;
}
Die beiden Schleifen sind also nicht voneinander abhängig, wie Deine Einrückung suggeriert, sie werden nacheinander ausgeführt, was in [mm]O(x)[/mm] liegt.
Im Gegensatz dazu ist hier die Einrückung korrekt
> for( i=0; i < x; i++ )
> for( j=i; j < x; j++ );
for (i=0; i<x; i++) {
for(j=i; j<x; j++) {
;
}
}
was tatsächlich zu einer Laufzeit von [mm]O(x^2)[/mm] führt.
Wichtig ist, den Code so zu sehen wie ein Compiler. Automatisches Source-Beautifying hilft dabei vielleicht?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:32 Do 29.09.2005 | | Autor: | Jacek |
Hi, Euch beiden erst einmal Danke.Warum ist in der Rechnung, die Du über die Reihen aufestellt hast:
[mm] \summe_{i=0}^{x-1} [/mm] = x² ? Ist das so definiert?
|
|
|
| |
|
Hallo Jacek,
> [mm]\summe_{i=0}^{x-1}{x} = x^2[/mm] ? Ist das so definiert?
Ja, so könnte man es sagen. Ich schreibe es mal ausführlicher hin:
[mm] $\sum_{i=0}^{x-1}{x} [/mm] = [mm] \underbrace{x+x+\dotsb+x}_{\begin{subarray}{l}\texttt{Addiere }x\texttt{ insgesamt }x\texttt{ mal:}\\\texttt{0tes Mal, 1tes Mal u.s.w.}\\\texttt{bis zum }x\texttt{-1-ten Mal.}\end{subarray}} [/mm] = x*x = [mm] x^2$
[/mm]
Viele Grüße
Karl
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:43 Do 29.09.2005 | | Autor: | Jacek |
Hmm, gut. Aber es gibt doch keinen Index i in der Reihe, was ja durch i=0 initialisiert wird... Damit habe ich Probleme...
|
|
|
| |
|
> Hmm, gut. Aber es gibt doch keinen Index i in der Reihe,
> was ja durch i=0 initialisiert wird... Damit habe ich
> Probleme...
Du kannst es dir an dieser Stelle ja auch wieder als eine Schleife in einem Programm vorstellen, z.B.:
| 1: |
| | 2: | /*input(x);*/
| | 3: | int k = x;
| | 4: | for(int i = Startwert; i < Endwert; i++)
| | 5: | x += k;
|
Also, hier ist es ja auch so, daß x Endwert-Startwert mal aufgerufen wird.
(Ok, das obige Code-Schnippsel beachtet vielleicht einige Spezialfälle nicht wie Startwert = 0, aber es geht mir nur um's Prinzip.)
x ist hier nicht direkt von i abhängig. 'i' bestimmt einfach nur wieviele Male das 'k' zum x dazuaddiert wird. Und genau dieser Sachverhalt ist es, den man auch in der vorigen mathematischen Schreibweise ausdrücken kann.
Oder lange Rede kurzer Sinn: Wenn Du 3 Schafe hast, kannst Du sie entweder mit 1,2,3 abzählen oder mit 32234354,32234355,32234356 oder sonst irgendwie. Es macht keinen Unterschied.
Grüße
Karl
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:11 Do 29.09.2005 | | Autor: | Jacek |
Dankeschön. Das war eine schwere Geburt...
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:49 Fr 30.09.2005 | | Autor: | Jacek |
Eine letzte Frage,zu der Schleife:
> for( i=0; i < x; i++ )
> for( j=i; j < x; j++ );
Da sind jetzt die Summen gebildet worden:
[mm] \summe_{i=0}^{x-1} \summe_{j=i}^{x-1}1
[/mm]
Aber woher kommt die 1?
Wirklich die letzte Frage.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:01 Fr 30.09.2005 | | Autor: | bazzzty |
> Eine letzte Frage,zu der Schleife:
> > for( i=0; i < x; i++ )
> > for( j=i; j < x; j++ );
>
> Da sind jetzt die Summen gebildet worden:
> [mm]\summe_{i=0}^{x-1} \summe_{j=i}^{x-1}1[/mm]
>
> Aber woher kommt die 1?
> Wirklich die letzte Frage.
He, die Frage ist a) gut, und b) würde uns ja keiner zwingen, zu antworten, also frag ruhig, dafür ist dieses Board ja da.
Zur Antwort ist: Zum Beispiel aus dem j++, der [mm]O(x^2)[/mm] mal ausgeführt wird unter Vernachlässigung aller anderen Befehle und Vergleiche. Oder aus dem Vergleich j<x.
Womit Du natürlich recht hast: In der inneren Schleife steht ja gar kein Befehl, der für die Laufzeit verantwortlich ist, aber ich habe ja schonmal eine andere Darstellung erwähnt: Die doppelte Schleife läßt sich auch schreiben als:
i=0;
while (i<x) {
j=i;
while (j<x) {
j++;
}
i++;
}
Wenn ich jetzt die Laufzeiten für Befehle zuweise (Zuweisung [mm]t_{\textrm{zuw.}}[/mm], Schleifenvergleich mit/ohne Sprung in die Schleife [mm]t_{\textrm{while+}}[/mm] bzw. [mm]t_{\textrm{while-}}[/mm], Inkrement [mm]t_{\textrm{inkr}}[/mm]), dann findet sich für die Laufzeit streng genommen ungefähr sowas:
[mm]T(x)=t_{\textrm{zuw.}}+t_{\textrm{while-}}+\sum_{i=0}^{x-1}\left(t_{\textrm{while+}}+t_{\textrm{zuw.}}+ t_{\textrm{while-}}+\sum_{j=i}^{x-1}\left[t_{\textrm{while+}}+t_{\textrm{inkr}}\right]+t_{\textrm{inkr}} \right)[/mm]
Interessant sind davon aber nur die Summanden, die [mm]O(x^2)[/mm] mal vorkommen, deren Aufwand ist konstant, und fällt damit in der [mm]O[/mm]-Notation unter den Tisch.
Man sieht also: Eine Schleife ist nie ganz leer: Mindestens das Schleifenkriterium wird geprüft, bei for-Schleifen kommt noch das Inkrement/Dekrement dazu.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:13 Fr 30.09.2005 | | Autor: | Jacek |
Hmmm, das geht echt ins Fundament.
Meine Frage war mehr mathematischer Natur.
Wir haben die Schleifen:
i=0;
while (i<x) {
j=i;
while (j<x) {
j++;
}
i++;
}
Jetzt habt ihr mir daraus eine schöne Formel gebildet:
[mm] \summe_{i=0}^{x-1} \summe_{j=i}^{x-1} [/mm] 1 = [mm] \summe_{i=0}^{x-1} \summe_{j=1}^{x-i} [/mm] 1 = [mm] \summe_{i=0}^{x-1} [/mm] (x-i) = [mm] \summe_{i=0}^{x-1} [/mm] x - [mm] \summe_{i=0}^{x-1}i [/mm] = ... = O(x²)
Der Rest -die Rechnung wird mir klar-, nur woher kommt diese 1 ?
Ich hoffe auf Antwort.
|
|
|
| |
|
Hallo Jacek,
Vielleicht sollten wir nochmal von vorne anfangen.
Wir hatten ja am Anfang folgendes stehen:
| 1: |
| | 2: | for( i=0; i < x; i++ )
| | 3: | for( j=i; j < x; j++ );
|
Das Semikolon am Ende markiert das Ende eines Befehls. In diesem speziellen Falle ist es das Ende der inneren und gleichzeitig der äußeren Schleife (muß natürlich nicht so sein). Der Schleifenkörper der inneren Schleife ist hier also "leer". Der Kompiler übersetzt das also lediglich in einen Code, der damit beschäftigt ist, die Index-Variablen ständig zu erhöhen. Eine solche Erhöhung (also z.B. 'c++') kann aber quasi "so schnell" vom Prozessor ausgeführt werden, daß der Aufwand für die Ausführung dieser Anweisung quasi vernachlässigbar ist. Diese Idee treibt man noch weiter. Wenn Du z.B. 44383394984475585487 mal hintereinander 'c++' ausführst ist der Aufwand immer noch konstant. Alle elementaren Befehlsfolgen dieser Art, die beim Messen der Ausführzeit Konstanten liefern(die eventuell immer noch vom System abhängig sind) (z.B. 1 ms), packt man deshalb in die Komplexitätsklasse [mm] $\mathcal{O}\left(1\right)$.
[/mm]
Deshalb habe ich bei der mathematischen Abschätzung in die innere Summe eine 1 gepackt. Ich hätte dort ebensogut eine Konstante $c [mm] \in \IR_{+}$ [/mm] schreiben können. Aber es hätte keinen Unterschied gemacht:
[mm] $\sum_{i=0}^{x-1}{\sum_{j=i}^{x-1}{c}} [/mm] = [mm] \sum_{i=0}^{x-1}{c\sum_{j=i}^{x-1}{\red{1}}} [/mm] = [mm] c\sum_{i=0}^{x-1}{\sum_{j=i}^{x-1}{1}} [/mm] = [mm] \mathcal{O}\left(x^2\right)$
[/mm]
Viele Grüße
Karl
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:13 Fr 30.09.2005 | | Autor: | Frank05 |
| 1: | for( i=0; i < x; i++ )
| | 2: | for( j=i; j < x; j++ );
|
> Der Kompiler übersetzt das also lediglich in
> einen Code, der damit beschäftigt ist, die Index-Variablen
> ständig zu erhöhen.
Das muss nicht sein. Es gibt keine festen Richtlinien, was der vom Compiler erzeugte Code an dieser Stelle machen muss. Ein intelligenter Compiler koennte dieses Konstrukt z.B. umwandeln in einen aequivalenten Code, der in O(1) laeuft:
Aus diesem Grund ist das obige Beispiel fuer eine Laufzeituntersuchung auch denkbar ungeeignet. Vielleicht wird es ein wenig klarer, wenn man das ganze mal etwas ausweitet:
| 1: | int calc(int x)
| | 2: | {
| | 3: | int i,j;
| | 4: | int anzahl = 0;
| | 5: | for (i = 0; i < x; i++) {
| | 6: | for (j = i; j < x; j++) {
| | 7: | anzahl++;
| | 8: | cout << "Durchlauf Nummer: " << anzahl << endl;
| | 9: | }
| | 10: | }
| | 11: | return anzahl;
| | 12: | }
|
> Alle elementaren Befehlsfolgen dieser Art, die
> beim Messen der Ausführzeit Konstanten liefern(die
> eventuell immer noch vom System abhängig sind) (z.B. 1 ms),
> packt man deshalb in die Komplexitätsklasse
> [mm]\mathcal{O}\left(1\right)[/mm].
Wenn ich die Ausfuehrzeit messe werde ich im Terminierungsfall immer einen Wert gemessen haben und der ist auch 'konstant' (weil es ja nur eine best. Zeit ist). 'Messen' sollten wir aus diesem Grund auch lieber anderen Wissenschaften ueberlassen
> Deshalb habe ich bei der mathematischen Abschätzung in die
> innere Summe eine 1 gepackt. Ich hätte dort ebensogut eine
> Konstante [mm]c \in \IR_{+}[/mm] schreiben können. Aber es hätte
> keinen Unterschied gemacht:
>
>
> [mm]\sum_{i=0}^{x-1}{\sum_{j=i}^{x-1}{c}} = \sum_{i=0}^{x-1}{c\sum_{j=i}^{x-1}{\red{1}}} = c\sum_{i=0}^{x-1}{\sum_{j=i}^{x-1}{1}} = \mathcal{O}\left(x^2\right)[/mm]
Hier vielleicht zum Verstaendnis nochmal zum Unterschied zwischen dem Code in Version 1 und 2:
Der Code fuer Version 1 muss nicht quadratisch werden, da der Compiler ihn optimieren koennte.
In Version 2 ist die Laufzeit, die du in Karls Summe einsetzen wuerdest die Summe der Laufzeiten der beiden Anweisungen. Wichtig ist hierbei, dass der Compiler keine Moeglichkeit hat die Anzahl der Durchlaeufe durch eine andere logische Sichtweise des Programms zu verbessern. Laesst man die Ausgabe mit cout weg sieht das schon wieder anders aus.
Ich weiss nicht, ob die Verstaendnisprobleme daher ruehren, aber man geht im Allgemeinen bei Laufzeitbetrachtungen dieser Art davon aus, dass der Code nicht frei von Seiteneffekten ist, und der Compiler nichts optimiert. Dann sind beide Versionen des Programms in [mm]\Theta(x^2) \subset \mathcal{O}(x^2)[/mm].
Vielleicht wird es damit jetzt ein wenig klarer.. und falls nicht hats hoffentlich auch nicht geschadet 
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:58 Sa 01.10.2005 | | Autor: | Jacek |
Danke, das hilft mir echt weiter!
Also könnte ich auch schreiben:
[mm] \summe_{i=0}^{x-1} \summe_{j=i}^{x-1}c [/mm] =...= O(x²), ja?!
Könnte ich für die Schleife:
for (int i=0; i<1; i++)
for (int j=0; j<i; i++);
die gleiche Form der Summennotation bitte bekommen?
Ich weiß, dass ebenfalls O(x²) raus kommt.
Beginnt das so?:
[mm] \summe_{i=0}^{x-1} \summe_{j=0}^{i-1} [/mm] c=... ?
|
|
|
| |
|
Hallo Jacek,
> Danke, das hilft mir echt weiter!
> Also könnte ich auch schreiben:
>
> [mm]\summe_{i=0}^{x-1} \summe_{j=i}^{x-1}c[/mm] =...= O(x²), ja?!
Ja, ich denke schon. Beachte aber auch die Anmerkungen von Frank05 und bazzzty. Es könnte sein, daß manche Compiler solche leeren Schleifenkonstrukte einfach wegoptimieren. Die Rechnung sagt dann nichts mehr aus, weil wir dann von einer falschen Annahme ausgehen.
> Könnte ich für die Schleife:
>
> for (int i=0; i<1; i++)
> for (int j=0; j<i; i++);
>
> die gleiche Form der Summennotation bitte bekommen?
> Ich weiß, dass ebenfalls O(x²) raus kommt.
>
> Beginnt das so?:
>
> [mm]\summe_{i=0}^{x-1} \summe_{j=0}^{i-1}[/mm] c=... ?
Eine Frage vorweg: Hast Du nicht eher folgendes Schleifenkonstrukt gemeint?
| 1: | for (int i=0; i < x; i++)
| | 2: | for (int j=0; j < i; j++)
| | 3: | {
| | 4: | cout << "huhu!\n";
| | 5: | } |
Wenn ja, dann ist's wohl die obige Summe:
[mm] $\sum_{i=0}^{x-1}{\sum_{j=0}^{i-1}{c}} [/mm] = [mm] c\sum_{i=0}^{x-1}{i} \mathop [/mm] = [mm] ^{\texttt{Gauss--Formel}} c\frac{\left(x-1\right)x}{2} [/mm] = [mm] \mathcal{O}\left(x^2\right)$.
[/mm]
Grüße
Karl
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:08 Sa 01.10.2005 | | Autor: | Jacek |
Könnte ich für die Schleife:
>
> for (int i=0; i<1; i++)
> for (int j=0; j<i; i++);
>
> die gleiche Form der Summennotation bitte bekommen?
> Ich weiß, dass ebenfalls O(x²) raus kommt.
Dieses war eine Neue Frage, um zu testen ob ich dieses richtig verstanden habe...
Kannst Du/Ihr mir bitte helfen?
|
|
|
| |
|
Hallo,
> > for (int i=0; i<1; i++)
> > for (int j=0; j<i; i++);
Aber so wie Du es vorher stehen hattest, ergibt es für mich nur wenig Sinn, da Du als Summe doch etwas völlig Anderes stehen hattest. Also gut, angenommen der Code oben wurde kompiliert. Ich bin jetzt mal das Betriebssystem:
| 1: |
| | 2: | for (int i=0; i<1; i++)
| | 3: | for (int j=0; j<i; i++);
|
Setze i = 0; 0 < 1;
Setze j = 0: 0 < 0 -> Abbruchbedingung erfüllt -> gehe aus der j-Schleife;
Erhöhe i um 1. 1 < 1 -> Abbruchbedingung erfüllt -> gehe aus der i-Schleife und mache etwas Anderes.
Ich würde sagen, die Laufzeit des obigen Code-Abschnitts liegt in [mm] $\mathcal{O}\left(1\right)$.
[/mm]
Gruß
Karl
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:50 So 02.10.2005 | | Autor: | Jacek |
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Hi, entschuldige die ganzen Unannehmlichkeiten...
Ich habe gestern ein nicht gesehen, ich meinte:
for (int i=0; i<x; i++)
for (int j=0; j<i; j++)
{...} } c
Macht das jetzt einen Unterschied?
|
|
|
| |
|
Hallo Jacek,
> for (int i=0; i<x; i++)
> for (int j=0; j<i; j++)
> {...}
>
> Macht das jetzt einen Unterschied?
Das habe ich dir vorhin beantwortet. Lies dir dort nochmal die Herleitung unten durch. Es gilt jedenfalls [mm] $\mathcal{O}(1)\subset\mathcal{O}\left(x^2\right)$, [/mm] was ein großer Unterschied in den Laufzeiten ist.
Viele Grüße
Karl
|
|
|
|
