Laufzeitkomplexität berechnen

Neue Frage »

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:

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:

package javao.n;

public class JavaoN {

    public static void main(String[] args) 
    {
        int [] array = {1,2,3,4,5,6,7,8,9,10}; 
        int sum = 0; 
        
        for (int i=0; i<array.length;i++)
        {
            sum += array[i]; 
        }
        System.out.println(sum);
    }
    
}



Meine Ideen:
Gibt es ein generelles Vorgehen um T(n) zu ermitteln?


Vielen Dank für Eure Hilfe :-)
 
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).
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). Zunge raus Zunge raus
Auf diesen Beitrag antworten »
Gast RE: Falsch!

Zitat:
Original von Gast
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). Zunge raus Zunge raus


---> bspw. ist im Falle von n = 1000000 dennoch die Schleife 10 Schritte lang (also limitiert, somit O(1))
 
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.
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
Auf diesen Beitrag antworten »
eulerscheZahl

Beispiel:
code:
1:
for(int i = 1; i < n; i *= 2) {...}

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.
Auf diesen Beitrag antworten »
Java_Beginner

Besten Dank, so wird das gleich verständlicher.
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »