Erste Schritte Weihnachtsbaum / Laufzeit O(n)

S

ShadowBSE

Gast
Hallo zusammen,

ich hätte eine Frage bezüglich meines Codes. Aufgabe ist es, einen Weihnachtsbaum mit der Laufzeit O(n) zu erzeugen. Leider habe ich die O Notation nicht wirklich verstanden und auch durch diverse Recherchen bin ich nicht erleuchtet worden... Nun muss ich meinen Code noch heute Abend einreichen und weiß halt nicht ob das richtig ist oder nicht. Wäre super, wenn mir jemand sagen könnte, ob dieser Code die Laufzeit O(n) hat und wenn nicht warum und wie man das beheben kann. Danke schonmal.

Java:
public class weihnachtsbaum {
static int i;
int n;
static int j;

public static void drawTree(int n)
{

int height = n;
int middle = (int) Math.ceil(n);


for (int i = 0; i<= height -1; i++)
{
	for (int j = 0; j<= middle-i; j++)
	{
	System.out.print(" ");
	}
	
	for (int j = middle - i+1; j <= middle ; j ++)
	{
	System.out.print("*");
	}
	
	for (int j = middle - i; j <= middle ; j ++)
	{
	System.out.print("*");
	}
	
	System.out.println();
}


if(height>9)
{
	for(int i = 0;i<=height-1 ;i++)
	{
	System.out.print(" ");
	}
	
	for(int i=height; i<=height; i++)
	{
	System.out.println("§$§");
	}
	
	for(int i = 0;i<=height-1 ;i++)
	{
	System.out.print(" ");
	}
	
	for(int i=height; i<=height; i++)
	{
	System.out.println("§$§");
	}
}


if(height<=9)
{
	for(int i = 0;i<=height-1 ;i++)
	{
	System.out.print(" ");
	}
	
	for(int i=height; i<=height; i++)
	{
	System.out.println(" $ ");
	}

}

}



public static void main(String[] args)
{
drawTree(19);

}

}
 
B

bygones

Gast
nein ist nicht O(n). Ziemlich einfach gesagt .- wenn du mehrere schleifen hast ist es nicht O(n). O(n) heisst lineare Laufzeit.

Als Tipp: Stell dir den Baum als leeres Rechteck vor mit einer gewissen Kantenlaenge X. in der obersten Zeile ist das mittlere Element ein *, in der 2. dann 3x*. D.h. in der erste zeile sind X - 1 zeichen leer, in der 2. X-3 etc

Grob gesagt, sieht man damit dass man mit einer schleife auskommt
 
S

ShadowBSE

Gast
Danke erstmal.
Im gesamten Code darf also nur eine also nur eine Schleife sein? Hm... Wüsste nicht wie ich es dann lösen kann. Hättest du vielleicht Lust mir kurz ein allgemeines Layout aufzuschreiben? Also nur die Methodenköpfe oder so?
 
M

Marcinek

Gast
Ohh.

Ich bin doof. Ich habe die äußere for-schleife nicht gesehen ;) :lol:
 
Zuletzt bearbeitet von einem Moderator:
S

ShadowBSE

Gast
Habe jetzt nochmal ein bisschen gebastelt und das ist das kürzeste worauf ich komme... Eine Lösung mit nur einer Schleife im ganzen Code will mir einfach nicht einfallen :(

Java:
public class weihnachtsbaum
    {
     
            public static void main (String argv[])
    {
            	drawTree(5);
    }
            	
            	
            public static void drawTree(int n)
            {
            	 
	            int i, height = n;	
	     
	            for (i=0; i < height; i++)
	            {
	                    for (int g = height; g > i; g--)
	                    {
	                            System.out.print (" ");
	                    }
	     
	                for (int y=-1; y < (i*2); y++)
	                    {
	                            System.out.print ("*");
	                    }
	     
	            System.out.print ("\n");
	            }
	     
	            for (int j=0; j < i; j++)
	            {
	                    System.out.print (" ");
	            }
	     
	            System.out.print ("|\n");
     
            }
    
    }
 
S

ShadowBSE

Gast
Mkay.
Hast du denn eine Idee wie ich meine Verschachtelung, also

Java:
 for (i=0; i < height; i++)
                {
                        for (int g = height; g > i; g--)
                        {
                                System.out.print (" ");
                        }
         
                    for (int y=-1; y < (i*2); y++)
                        {
                                System.out.print ("*");
                        }


auflösen kann? M.m.n. ist es eigentlich garnicht möglich, da i < height immer zwingend erfüllt sein muss, damit die Zeichenschritte passieren können. Und da die Höhe des Baumes ja beliebig ist, müssen die Zeichenschritte ja auch in einer Schleife passieren. Somit brauche ich zwingend eine Schleife in einer Schleife?!
 

Antoras

Top Contributor
Edit: Hier stand Müll.
Besser:

Im O-Kalkül ist es irrelevant wie lange eine Operation dauert, es geht nur um die Anzahl der Operationen. Ein Baum der Höhe n ist in n Operationen (also O(n)) gezeichnet. Die inneren Schleifen kannst du als Operation f ansehen, die immer eine Konstante Laufzeit hat.

Etwas anderes ist es wenn du die Laufzeit aller gezeichneten Zeichen haben möchtest. Diese wäre O(n*m), da du n Reihen und m Spalten hast.
 
Zuletzt bearbeitet:

Final_Striker

Top Contributor
Also für feste Werte würde das gehen aber bei dynamischen wüsste ich jetzt auch nicht, wie man das unkompliziert in O(n) machen soll.

Kannst ja in der Schleife mit if/else Bedingungen arbeiten.
 

HimBromBeere

Top Contributor
Noch ein Wort zur Ordnung deines Programmes:

Bei der Ordnung ist es eigtl. wurscht, (wie bereits erwähnt), wie lange eine Operation dauert. Das bedeutet aber zwangsläufig, dass es keine Ordnung vom Typ (n, m) gibt, sondern nur n². Das heißt, die Laufzeit deines Programmes ändet sich quadratisch mit der Anzahl verarbieteter Datensätze (n).
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
T Java Weihnachtsbaum + Rahmen Java Basics - Anfänger-Themen 1
Ellachen55 Weihnachtsbaum in Eclipse programmieren Java Basics - Anfänger-Themen 6
D Weihnachtsbaum implementieren gescheitert. Java Basics - Anfänger-Themen 2
B Erste Schritte Weihnachtsbaum zeichnen Java Basics - Anfänger-Themen 6
C Weihnachtsbaum zeichnen lassen Java Basics - Anfänger-Themen 10
Detlef Bosau Nachladen von Klassen zur Laufzeit Java Basics - Anfänger-Themen 24
E Alter (Laufzeit) berechnen Java Basics - Anfänger-Themen 11
W Array zur Laufzeit bearbeiten? Java Basics - Anfänger-Themen 31
D Objekterzeugungen mit zur Laufzeit variierenden Attributen Java Basics - Anfänger-Themen 7
J GroupLayout zur Laufzeit erweitern Java Basics - Anfänger-Themen 1
B Übersetzungszeit und Laufzeit Java Basics - Anfänger-Themen 3
amgadalghabra Die vier Sortieralgorithmen die durchschnittliche Laufzeit in Millisekunden Java Basics - Anfänger-Themen 37
U Dijkstra Algorithmus Laufzeit Java Basics - Anfänger-Themen 3
S Laufzeit Quicksort wenn alle Elemente gleich sind Java Basics - Anfänger-Themen 4
L Anzahl der Elemente key in einem Array mit log(N) Laufzeit Java Basics - Anfänger-Themen 4
S Interpreter-Fehler Endlosschleife zur Laufzeit aber warum? Java Basics - Anfänger-Themen 15
J JavaFX Label,Button zur Laufzeit Java Basics - Anfänger-Themen 30
H Laufzeit Java Basics - Anfänger-Themen 11
C Laufzeit eines Sortier-Algorithmus ermitteln Java Basics - Anfänger-Themen 4
L Objekt Typ zur Laufzeit ermitteln Java Basics - Anfänger-Themen 1
J Datei im Package zur Laufzeit editieren Java Basics - Anfänger-Themen 1
M Quicksort Laufzeit langsam Java Basics - Anfänger-Themen 5
M Quicksort Laufzeit langsam Java Basics - Anfänger-Themen 0
R Objekte zur Laufzeit in Schleife erzeugen und in ArrayList ablegen Java Basics - Anfänger-Themen 4
C Laufzeit von Stack Operation Java Basics - Anfänger-Themen 5
D Laufzeit von einfachem Programm Java Basics - Anfänger-Themen 21
J Laufzeit berechnen/Laufzeitanalyse Java Basics - Anfänger-Themen 2
M Input/Output Datei in Laufzeit-JAR kopieren Java Basics - Anfänger-Themen 6
V Laufzeit Java Basics - Anfänger-Themen 23
G Laufzeit/ O/Θ-Notation einer Treeset Methode Java Basics - Anfänger-Themen 0
W Klassen [GELÖST] Objekte während der Laufzeit mit neuen veränderten Werten beliebig oft initialisieren Java Basics - Anfänger-Themen 2
M Erste Schritte Code zur Laufzeit ändern lassen Java Basics - Anfänger-Themen 3
C Klassen aus einem Package ermitteln und per Laufzeit laden Java Basics - Anfänger-Themen 17
J Objekte zur Laufzeit erzeugen und direkt verwenden Java Basics - Anfänger-Themen 9
M Möglich? Methode aufrufen deren Bezeichner zur Laufzeit durch einen überg. String festgelegt wird Java Basics - Anfänger-Themen 3
K JLabel zur Laufzeit dynamisch erzeugen Java Basics - Anfänger-Themen 7
M Methoden miteinander verbinden (Laufzeit) Java Basics - Anfänger-Themen 6
llabusch Interface Layout eines Labels während der Laufzeit ändern Java Basics - Anfänger-Themen 0
Streeber reale Laufzeit meines Programms ausgeben Java Basics - Anfänger-Themen 1
D Algorithmus zu gegebener Laufzeit implementieren Java Basics - Anfänger-Themen 1
R Variablen Datentyp erst während Laufzeit festlegen Java Basics - Anfänger-Themen 6
S Klassentyp zur Laufzeit ändern? Java Basics - Anfänger-Themen 3
M Laufzeit und O-Notation Java Basics - Anfänger-Themen 3
M Variablen Variable zur Laufzeit erzeugen Java Basics - Anfänger-Themen 3
A Laufzeit von verschachtelter for-Schleife Java Basics - Anfänger-Themen 4
B Variablen Instanz von Enum zur Laufzeit erstellen und zuweisen Java Basics - Anfänger-Themen 2
L Panels zur Laufzeit ändern Java Basics - Anfänger-Themen 2
A Laufzeit Java Basics - Anfänger-Themen 11
M Methodennamen zur Laufzeit ausgeben Java Basics - Anfänger-Themen 5
F JTable zur laufzeit füllen Java Basics - Anfänger-Themen 7
P GUI - Layout per Laufzeit erstellen/verändern? Java Basics - Anfänger-Themen 6
N Variablen VariableNamen auswirkung auf Laufzeit Java Basics - Anfänger-Themen 3
R Rekursionsformel für Laufzeit von Algorithmus Java Basics - Anfänger-Themen 3
J Erste Schritte Zinseszinsberechnung Ermittlung Laufzeit Java Basics - Anfänger-Themen 3
S Laufzeit bei rekursiver Methode messen Java Basics - Anfänger-Themen 6
E Laufzeit verkürzen Java Basics - Anfänger-Themen 14
A Threads Zur Laufzeit hinzufügen/entfernen Java Basics - Anfänger-Themen 10
D Classpath compiler zur Laufzeit aufrufen & lib-classpath Java Basics - Anfänger-Themen 6
E Input/Output Inputstream während der Laufzeit füllen Java Basics - Anfänger-Themen 2
B Laufzeit berechnen? Java Basics - Anfänger-Themen 7
S Klasse bei Laufzeit laden? Java Basics - Anfänger-Themen 2
B Klassen Objekte während der Laufzeit dynamisch anlegen Java Basics - Anfänger-Themen 8
K jButton zur Laufzeit hinzufügen Java Basics - Anfänger-Themen 22
D globale Variablen zur Laufzeit erzeugen Java Basics - Anfänger-Themen 5
A Frage zur Laufzeit / Optimierung Java Basics - Anfänger-Themen 2
N Laufzeit in Nanosekunden - in Minuten umrechnen Java Basics - Anfänger-Themen 6
alderwaran objekthierarchie darstellen während der laufzeit Java Basics - Anfänger-Themen 2
G Objekte von Klassen die erst zur Laufzeit bekannt sind erstellen Java Basics - Anfänger-Themen 6
B Frage zur Laufzeit Java Basics - Anfänger-Themen 2
Luk10 Variablen zur Laufzeit ändern! Java Basics - Anfänger-Themen 7
G JAR zur Laufzeit nachladen Java Basics - Anfänger-Themen 2
S JDialog resize zur Laufzeit PROBLEM!!! Java Basics - Anfänger-Themen 5
E Pfad zu einem gif-Bild wird zur Laufzeit nicht gefunden Java Basics - Anfänger-Themen 5
A Applet Bild zu laufzeit hinzufügen Java Basics - Anfänger-Themen 4
C Frage zu Syntax-,Laufzeit-, Semantikfehler Java Basics - Anfänger-Themen 3
R JVM zur laufzeit manipulieren? Java Basics - Anfänger-Themen 4
S Zur Laufzeit Strings Compilieren Java Basics - Anfänger-Themen 5
A Objekte während der Laufzeit erstellen Java Basics - Anfänger-Themen 3
A Objektzugriff zur Laufzeit ändern Java Basics - Anfänger-Themen 20
G Text eines JLabels zur Laufzeit ändern Java Basics - Anfänger-Themen 4
M Laufzeit von Programmen Java Basics - Anfänger-Themen 3
A Jar-Archive zur Laufzeit erstellen Java Basics - Anfänger-Themen 3
G Zu Laufzeit von Tastatur einlesen Java Basics - Anfänger-Themen 11
E Einen String auch über die Laufzeit hinaus speichern Java Basics - Anfänger-Themen 4
A Neue Objekte zur Laufzeit erzeugen Java Basics - Anfänger-Themen 5
D Locale zur Laufzeit über JComboBox laden? Java Basics - Anfänger-Themen 17
S Ausdruck zur Laufzeit auswerten Java Basics - Anfänger-Themen 10
G Anzahl Textfelder zur Laufzeit verändern. Java Basics - Anfänger-Themen 4
Z Benutzerdaten währen Laufzeit speichern Java Basics - Anfänger-Themen 2
K JProgressbar, zur laufzeit steuern Java Basics - Anfänger-Themen 7
V Vektoren zur Laufzeit erzeugen Java Basics - Anfänger-Themen 7
N zur Laufzeit gefundene class-Datei verwenden - wie geht das? Java Basics - Anfänger-Themen 2
G Look and Feel zur Laufzeit ändern Java Basics - Anfänger-Themen 2
A Text einer JComboBox während der Laufzeit ändern ? Java Basics - Anfänger-Themen 4
K Chart zur Laufzeit erstellen und aktualisieren Java Basics - Anfänger-Themen 2
G JAR: Externe Dateien zur Laufzeit aufrufen Java Basics - Anfänger-Themen 12
C Variablen zur Laufzeit erstellen? Java Basics - Anfänger-Themen 14
B Warum hat dieser einfache Algorithmus lineare Laufzeit? Java Basics - Anfänger-Themen 3
M JButton zur laufzeit erzeugen/ löschen Java Basics - Anfänger-Themen 3
B Laufzeit und Übersetzungszeit Java Basics - Anfänger-Themen 11

Ähnliche Java Themen

Neue Themen


Oben