Frage zur for- Schleife

[sahneboy]

Hallo,

ich interessiere mich sehr für Java und ich wollte mich schon vor meinem Studiumstart etwas damit beschäftigen. Ich bin gerade bei dieser for Schleife hängen geblieben.

for( int i = 0; i < n; i++)
for( int k = 0; k < i; k++)
x = x + 1;

Welchen Wert hat x nach der Ausführung der Schleife, wenn man mit 0 anfängt( also x wird mit 0 initialisiert)?
Zu welcher Komplexitätsklasse gehört das Programmfragment? Ich habe kein Ahnung was hier gefragt wird. In meinem Buch/Internet finde ich nirgends was zu Komplexitätsklassen. Kann mir jemand was dazu linken? Finde nichts passendes dazu.

Danke schonmal

 

[Robinson97]

Was für einen Wert hat den n ?

 

[sahneboy]

eine natürliche Zahl. Einen genauen Wert gibt es nicht.

 

[Robinson97]

Und wie willst du dan x haben, wenn du n nicht kennst ????:L

 

[sahneboy]

Wie wärs mit einer Zahl ausdenken? Oder anders gefragt -> wie oft wird die innere for schleife ausgeführt, wenn es abhängig von n ist?

 

[Robinson97]

Die Schleife geht so lange wie i < n. In deinem Beispiel hast du zwei verschachtelte for-schleifen. Die innere ist von der Äußeren abhängig das heißt die Schleife läuft nicht so lange durch wie x = n ist; Nehmen wir als Beispiel für n die Zahl 10. Dan ist am Ende x nicht 10 sondern 45. Oder hab ich deine Frage falsch verstanden?

 

[sahneboy]

Oder anders gefragt -> wie oft wird die innere for schleife ausgeführt, wenn es abhängig von n ist?​

 

[Dompteur]

...In meinem Buch/Internet finde ich nirgends was zu Komplexitätsklassen. Kann mir jemand was dazu linken? Finde nichts passendes dazu.

Ich hatte da mehr Glück bei der Suche in meinem Internet:
Komplexitätsklasse – Wikipedia
Komplexitätstheorie – Wikipedia

 

[Major_Sauce]

Nabend,

mal nebenbei:

Rekursive Operationen können auch anders geschrieben werden:

x = x + 1;
//das selbe wie
x++;
//oder
x += 1;

zu deiner Frage:

Wir gehen mal aus, dass x am Anfang == 0, dadurch wird x bei jedem Schleifendurchlauf der 2. Schleife erhöht.
Wenn wir noch einmal eine Schleife außenrum haben, dann wird das noch mal "n" genommen, da diese auch noch so oft ausgeführt wird.

--> x = xStart + n * k;

Da kannst nun "n" und "k" einsetzen und voila hast du dein Ergebnis.
Ach ja, xStart ist der Betrag von x vor dem Durchlauf der beiden Schleifen...

mfg Major

 

[strußi]

du kannst auch noch eine schleife für n drum rum packen, und dir nach jedem druchgang den wert für x ausgeben lassen

dabei ist k immer um eins kleiner als i

public static void main( String[] args){
        int x =0;
        for( int n =0; n <100; n++){
            for( int i =0; i <n; i++){
                for( int k =0; k <i; k++){
                    x++;
                }
            }
            System.out.println("n: " +n +"   x: " +x);
                  
        }
    }

 

[sahneboy]

Zu der Frage: Welchen Wert hat x nach Ausführung des Programmfragmentes, falls x vorher mit 0 initialisiert wurde?
Nehmen wir mal an n= 100, k=5.

dann wäre x= 0 + 100 * 5
x=500 ?

 

[strußi]

sollte so sein, aber so wie die schleifen aufgebaut sind wirst du den wert nur erreichen wenn du x mit 499 initialisierst

 

[CSHW89]

Ist doch ganz einfach. Die äußere Schleife wird n-mal durchlaufen, dabei ist im 1. Durchlauf i=0, im 2. i=1, usw. bis zum n. Durchlauf i=n-1. So, die innere Schleife wird dann immer abhängig von i, genau i mal durchlaufen. Also Anzahl der Inkrementierungen von x ist:
sum(i, i=0..n-1) = 0+1+2+...+(n-1) = ???
Die Fragezeichen kann man auch ausrechnen. Das überlasse ich mal dir. Komplexitätsklasse siehe auch die O-Notation: Landau-Symbole – Wikipedia.

lg Kevin