Wachstumsordnung

V

virtual12

Aktives Mitglied
Ich soll die Wachstumsordnung folgender Funktion ermitteln. Meine Vermutung ist quadratisch wegen der beiden if Schleifen, bin mir aber ziemlich unsicher. Hier die Funktion:
Java: 
  public static String method1(int N){
        if (N == 0) return "";
        String temp = method1(N/2);
        if (N%2 == 0) return temp + temp;
        else return temp + temp + "x";
    }
 
Zuletzt bearbeitet von einem Moderator:
K

kneitzel

Gast
if ist keine Schleife. Daher ist diese Vermutung so falsch.

Auch zwei schleifen nacheinander wäre nicht quadratisch....

Also noch andere Vermutungen?
 
K

kneitzel

Gast
Geh die Funktion doch einfach einmal durch. N=1, N=2, N=3, N=4, .... Was passiert jeweils in der Funktion? Das Entscheidende ist der rekursive Aufruf mit N/2. Also wie viele Aufrufe von der Funktion gibt es je nach N?

Und dann musst Du schauen, was für einer Funktion das entspricht und schon hast Du das Ergebnis.
 
K

kneitzel

Gast
Du siehst doch die Rekursion? In der Funktion ist wieder ein Funktionsaufruf. Und die Anzahl der Rekursiven Aufrufe ist abhängig von N. Daher ist jetzt doch die Frage, wie steigt die Komplexität mit N an.

Dazu muss man die Funktion ermitteln, die eben genau dies angibt. Wie kommst Du auf das linear? Einfach nur geraten?
 
V

virtual12

Aktives Mitglied
Ich habe nur N/2 gesehen und die Rekursion nicht beachtet. Wie komme ich auf diese Funktion? Woran erkenne ich die Anzahl der rekursiven Aufrufe? Mir ist das noch nicht ganz klar. Kannst du mir noch genauer erklären?
 
K

kneitzel

Gast
Ich würde die Funktion einfach mit verschiedenen Werten durchspielen um dann evtl. etwas zu erkennen. Wenn Deine Vermutung mit linear stimmen würde, müsste ja graphisch dargestellt eine Linie rauskommen. Somit könnte eine graphische Visualisierung helfen.

Mit ewas Erfahrung sieht man es aber evtl. auch, da man den Vergleich mit bekannten Abläufen hat.

Wichtig ist: An so einer Operation N/2 sieht man es nicht direkt. Das ist ja eine fixe Operation hat also ein O(1) - ist ja auch klar: Ist ja nur ein Bit-Verschieben. Aber die Operation ist dennoch wichtig für die Bewertung.
 
V

virtual12

Aktives Mitglied
Danke für deine Erklärungen. Würde aber auch jetzt bei einem linearen Anstieg bleiben, weil bei mir folgende Werte rauskommen: Aber vielleicht habe ich auch etwas völlig falsch verstanden?
N=0 ist leerer String
N=1 ist x
N=2 ist 2x
N=3 ist 3x
N=4 ist 4x
N=5 ist 5x
usw.
Stimmt das oder liege ich völlig falsch?
 
K

kneitzel

Gast
Das ist nicht, was ich meinte. Mich interessiert nicht die Ausgabe der Funktion. Wir wollen doch das Laufzeitverhalten der Funktion ermitteln. Daher ist die Ausgabe relativ egal an dieser Stelle.

Für das Laufzeitverhalten zählen Schleifen und Rekursionen. Schleifen haben wir nicht aber eine Rekursion. Also müssen wir herausfinden, wie oft method1 aufgerufen wird. Daher können wir die Funktion vereinfachen und alles, was zum generellen Laufzeitverhalten nicht beiträgt, weglassen. Dann hätten wir diese Funktion:

Code: 
public static void method1(int N) {
       if (N ==0) return;
       method1(N/2);
   }

Wie viele method1 Aufrufe habe ich bei method1(0), method1(1), method1(2), ...

Und was für ein Laufzeitverhalten siehst Du da dann?

Aber die Ausgabe ist wohl richtig erfasst. Die Funktion dürfte einen String zurück geben mit N mal "x".
Jetzt wäre nur noch interessant zu wissen, wieso man das so machen könnte statt mit einer for Schleife?

Konrad
 
stg

stg

Top Contributor
Naja, die Aufgabe ist in sofern echt gemein gestellt, da die String-Concatenierung mit zunehmender Größe des Strings natürlich auch recht aufwändig wird.
Hier werden ja andauernd immer größere char-Arrays erstellt und deren Inhalte hin- und hergeschaufelt.
Vermutlich war dem Aufgabensteller das gar nicht bewusst, oder es handelt sich wirklich um eine "Fangfrage".
 
V

virtual12

Aktives Mitglied
Hoppla, dann war ich wohl auf dem falschen Weg. Spontan würde ich sagen, dass die Methode 1 jeweils einmal aufgerufen wird, was einer konstanten Wachstumsordnung entsprechen würde.
 
V

virtual12

Aktives Mitglied
Was meinst du, dass die String Concatenierung immer aufwendiger wird? Woran erkenne ich, dass immer größere char Arrays erstellt werden?
 
K

kneitzel

Gast
Über den Punkt habe ich auch schon nachgedacht. Generell ist die Funktion für große N recht blöd. Strings so zusammen zu fügen ist das sehr schlecht. Aber im vergleich zu einer for Schleife, die Strings zusammen fügt, hat sie noch gewisse Vorteile :)

Aber klar - es gibt deutlich bessere Lösungen so einen String zu erzeugen (Stringbuilder z.B.)

Ich denke, der Aufgabensteller wollte diesen Aspekt nicht wirklich betrachten. Aber mit einer solchen Betrachtung hätten wir dann ja auch hier ein O(n). Wobei das auch Unsinnig ist, denn mit sehr großem n ist die Funktion auch auf heutigen Rechnern nicht mehr praktikabel. Und wenn n ehh nur kleine Werte annimmt, dann muss ich da nichts bestimmen. Dann mache ich einen Unit-Tests mit n = 100 und sehe, ob die Laufzeit stimmig ist.

Und die Frage ist, in wie weit der Punkt wirklich ignoriert werden kann. Evtl. war da ein Lehrer stolz, denn er hat ein O(n) in O(log(n)) gelöst, was quatsch ist. Denn es wird immer auf einen Speicherbereich hinaus laufen, der sich linear vergrößert (N*2 Bytes da der String in UTF-16 gespeichert wird) und dieser Speicherbereich muss mit einem Wert gefüllt werden. Damit hat man rein logisch immer ein O(n) und kann da nie drunter kommen.

Aber haben wir damit jetzt den TE nicht endgültig verwirrt?
 
K

kneitzel

Gast
Also die methode1 wird natürlich mit steigendem N immer öfter aufgerufen. Aber das ist logarithmisch. Dieses Vorgehen entspricht in etwa der Suche in einem sortierten Array oder in einem ausbalanzierten Binären Suchbaum.
N wird ja immer halbiert. Also beim sortierten Array entspricht das dann immer dem Wechsel zu einer Seite und der erneuten Halbierung u.s.w. Oder im Suchbaum geht man immer eine Ebene tiefer und blendet damit ca. die Hälfte der Werte aus.

Also method1(0) -> 1 Aufruf (halt nur der direkte Aufruf)
method(1): ist der eigentliche Aufruf und noch der method1(1/2) was method1(0) entspricht: 2 Aufrufe
method(2): 1 + method(1) = 3 Aufrufe
Sieht bisher noch linear aus, aber schauen wir mal weiter:
method(3): 1 + method(1) = 3 Aufrufe
method(4): 1 + method(2) = 4 Aufrufe
method(5): 1 + method(2) = 4 Aufrufe
method(6): 1 + method(3) = 4 Aufrufe
==> Hier erkennt man dann jetzt doch deutlich, dass das lineare nicht länger stimmt. Meine reduzierte Funktion hat somit O(log(n))

Aber ich habe ja etwas weggelassen - und das ist die String Concatenation. Und die hat tatsächlich O(n). Hier ist die Frage, ob dies vernachlässigt werden sollte oder nicht, denn das Beispiel ist da ansonsten sehr schlecht gewählt.
 
V

virtual12

Aktives Mitglied
Nein, die String Concatenation soll nicht vernachlässigt werden. Wir haben nämlich noch als Tipp bekommen, dass wir bedenken sollen, dass der Zeitaufwand zum Verketten zweier Strings proportional zur Summe ihrer Längen ist.
 
JStein52

JStein52

Top Contributor
Leute, Leute. Es geht doch hier um die Rekursionstiefe und nicht darum was diese Stringconcatenation macht. Verwirrt den armen Kerl nicht so. Es ist schlicht und einfach so bei Verdoppelung von N steigt die Rekursionstiefe um 1 an !
 
K

kneitzel

Gast
Und genau da hast Du dann nicht mitbekommen, dass der TE explizit auch die String Concatenation mit betrachten soll. Und damit hat man dann halt O(n log(n)).

Konrad
 
JStein52

JStein52

Top Contributor
Doch, das hatte ich gelesen, aber das glaube ich nicht wirklich. ;) ich glaube eher dass der String mit n mal x der da rauskommt verwirren soll. Aber vielleicht irre ich mich.
 
V

virtual12

Aktives Mitglied
Also es steht konkret folgendes in der Aufgabenstellung:
  1. Ermitteln Sie die Wachstumsordnungen der Funktionen. Denken Sie daran, dass der Zeitaufwand zum Verketten zweier Strings proportional zur Summe ihrer Längen ist.

    Wie ist das nun zu verstehen? Und was muss ich jetzt machen? Im Moment bin ich tatsächlich etwas verwirrt.
 
JStein52

JStein52

Top Contributor
Ja ok. Dann hatte ich mich geirrt und er meint es wirklich ernst dass ihr das String kopieren auch mitbetrachten sollt. In dem Fall siehe oben !
 

Aktuelle Jobs

Neue Themen


Oben