Berechnung Zeitkomplexität eines Methodenaufrufes innerhalb eines Methodenaufrufes

Question

http://imgur.com/a/efinr

Also habe ich mit dem Erstellen von Methoden in Java beauftragt worden, die grundlegenden Operationen (addieren, subtrahieren, multiplizieren) tun mit HugeIntegers (den Arrays sind, dass das Haus Ziffern in ihren Indizes wäre zB 1111 [1,1,1,1]).

Nachdem wir unseren Code geschrieben haben, werden wir gebeten, die Zeitkomplexität zu analysieren (dh. Big Theta Komplexitätsklassen) und ich habe ein wenig Mühe, einen Teil meines Codes zu analysieren (siehe Link).

Ich weiß, dass die X1.add (Diff) mir großen Theta (n) geben wird, wobei n die Anzahl der Ziffern des HugeInteger ist, und compareTo (x2) wird mir auch große Theta (n) geben. Der Inhalt innerhalb der while-Schleife ist ebenfalls groß theta (n). Nun, ist die gesamte Zeitkomplexität dieses Code-Teils Theta von (n^3) oder wäre es n^2? Ich habe ein bisschen Probleme mit der while-Schleife, da ich nicht sicher bin, ob die n's addieren oder multiplizieren sollen. Ich weiß, dass, was auch immer dieses Ergebnis ist, mit dem n innerhalb der While-Schleife multipliziert wird.

Jede Hilfe ist sehr, sehr geschätzt. Ich habe den Großteil der Woche damit verbracht.

Answer 1

Der Zustand der Schleife wird einmal pro Schleifeniteration ausgeführt. Der Inhalt der Schleife wird ebenfalls einmal pro Schleifeniteration ausgeführt. So können Sie diese hinzufügen. Multiplizieren Sie dann natürlich mit der Anzahl der Schleifenläufe. Wenn die Bedingung (n) ist und der Schleifenkörper (n) ist, dann sind sie zusammen (n). Wenn die Schleife (n) mal läuft, dann ist die Summe (n^2).