Informatiker Board | Druckvorschau: Laufzeitkomplexität berechnen

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Praktische Informatik (http://www.informatikerboard.de/board/board.php?boardid=6)
---- Algorithmen (http://www.informatikerboard.de/board/board.php?boardid=17)
----- Laufzeitkomplexität berechnen (http://www.informatikerboard.de/board/thread.php?threadid=2293)

Geschrieben von Björn am 16.05.2015 um 22:54:

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 :-)

Geschrieben von eulerscheZahl am 17.05.2015 um 17:33:

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).

Geschrieben von Gast am 07.09.2015 um 19:23:

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

Geschrieben von Gast am 07.09.2015 um 19:24:

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

---> bspw. ist im Falle von n = 1000000 dennoch die Schleife 10 Schritte lang (also limitiert, somit O(1))

Geschrieben von eulerscheZahl am 08.09.2015 um 14:50:

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.

Geschrieben von Java_Beginner am 01.02.2016 um 10:12:

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

Geschrieben von eulerscheZahl am 01.02.2016 um 13:17:

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.