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

Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » Laufzeitkomplexität berechnen » Antwort erstellen » Hallo Gast [Anmelden|Registrieren]

Antwort erstellen
Benutzername: (du bist nicht eingeloggt!)
Thema:
Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33
smileWinkDaumen hoch
verwirrtAugenzwinkerngeschockt
Mit ZungeGottunglücklich
Forum Kloppebösegroßes Grinsen
TanzentraurigProst
TeufelSpamWillkommen
LehrerLOL HammerZunge raus
Hilfe 
aktuellen Tag schließen
alle Tags schließen
fettgedruckter Textkursiver Textunterstrichener Text zentrierter Text Hyperlink einfügenE-Mail-Adresse einfügenBild einfügen Zitat einfügenListe erstellen CODE einfügenPHP CODE farbig hervorheben
Spamschutz:
Text aus Bild eingeben
Spamschutz

Die letzten 8 Beiträge
Java_Beginner

Besten Dank, so wird das gleich verständlicher.
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.
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
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.
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))
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
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).
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 :-)