Erste Schritte Weihnachtsbaum / Laufzeit O(n)

[ShadowBSE]

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.

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

}

}

 

[bygones]

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

 

[ShadowBSE]

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?

 

[Marcinek]

Ohh.

Ich bin doof. Ich habe die äußere for-schleife nicht gesehen 😉 :lol:

 

[ShadowBSE]

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 🙁

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");
     
            }
    
    }

 

[Final_Striker]

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?

Nein, du darfst nur keine verschachtelten for-Schleifen haben.

 

[ShadowBSE]

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

 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]

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.

 

[Final_Striker]

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]

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