Registrierung Kalender Mitgliederliste Teammitglieder Suche Häufig gestellte Fragen Zur Startseite

Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » Laufzeitkomplexität berechnen » Hallo Gast [Anmelden|Registrieren]
Letzter Beitrag | Erster ungelesener Beitrag Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen
Neues Thema erstellen Antwort erstellen
Zum Ende der Seite springen Laufzeitkomplexität berechnen
Autor
Beitrag « Vorheriges Thema | Nächstes Thema »
Björn
unregistriert
Laufzeitkomplexität berechnen Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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 :-)
16.05.2015 22:54
eulerscheZahl eulerscheZahl ist männlich
Foren Gott


Dabei seit: 04.01.2013
Beiträge: 2.859

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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

__________________
Syntax Highlighting fürs Board (Link)
17.05.2015 17:33 eulerscheZahl ist offline Beiträge von eulerscheZahl suchen Nehmen Sie eulerscheZahl in Ihre Freundesliste auf
Gast
unregistriert
Falsch! Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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
07.09.2015 19:23
Gast
unregistriert
RE: Falsch! Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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))
07.09.2015 19:24
eulerscheZahl eulerscheZahl ist männlich
Foren Gott


Dabei seit: 04.01.2013
Beiträge: 2.859

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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.

__________________
Syntax Highlighting fürs Board (Link)
08.09.2015 14:50 eulerscheZahl ist offline Beiträge von eulerscheZahl suchen Nehmen Sie eulerscheZahl in Ihre Freundesliste auf
Java_Beginner
unregistriert
Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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
01.02.2016 10:12
eulerscheZahl eulerscheZahl ist männlich
Foren Gott


Dabei seit: 04.01.2013
Beiträge: 2.859

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

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.

__________________
Syntax Highlighting fürs Board (Link)
01.02.2016 13:17 eulerscheZahl ist offline Beiträge von eulerscheZahl suchen Nehmen Sie eulerscheZahl in Ihre Freundesliste auf
Java_Beginner
unregistriert
Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

Besten Dank, so wird das gleich verständlicher.
02.02.2016 09:17
Baumstruktur | Brettstruktur
Gehe zu:
Neues Thema erstellen Antwort erstellen
Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » Laufzeitkomplexität berechnen