Algorithmus zu einer gegebenen Laufzeit erstellen

Zitat von dobby

Ich dachte bei dem n^2 könnte man 2 inereinder geschacghtelte schleifen machen, die jeweils n mal durchlaufen werden und innen drin dann etwas berechnen, allerdings komme ich nicht drauf.

Das stimmt auch so. Was heißt "du kommst nicht drauf"?

Allgemein kannst du für eine Formel f(n) übrigens immer den Algorithmus

for i = 1 to f(n){
print "Hello World"
}

angeben. Das stimmt immer, unabhängig von f(n) (sofern es in der Angabe keine weiteren Anforderungen gibt). Die intendierte/gewünschte Lösung ist zwar meistens eine andere, aber ich wollte es als Notlösung (z.B. bei Ratlosigkeit bei Prüfungen) erwähnt haben.

Zitat von dobby

Ja, das Problem ist, wie was muss ihc in rumpf der zweiten schleife schreiben. Ich hab echt shcon viel ausprobiert über fakultäten, immer 2 addieren, mit den zählvariablen der schleife arbeiten, allerdings kommt bei mir nie das richtige ergebnis heraus.

Achso, du sollst tatsächlich den Wert der Formel berechnen. Sorry, hab gedacht das wäre ebenfalls eine Laufzeitangabe. War verwirrt weil die Beispiele die ich immer lösen musste immer nur einen beliebigen Algorithmus verlangt haben der eine bestimmte Laufzeit hat.

Also für n^2 kannst du einfach x = 1 setzen und dann in einer Schleife n mal um 1 Bit nach links shiften (man könnte natürlich auch gleich n mal shiften, aber dann kommt man nicht auf die geforderte Laufzeit). Damit die Laufzeit des Shifts von n abhängt, muss er so implementiert sein dass er bei Stelle 0 anfängt und abbricht, sobald zum ersten mal 1 geshiftet wurde. Die Schleife hat Zeit n und jedes Shiften braucht Zeit O(ld(x)) wenn x der aktuelle Wert ist (da eine Zahl x mit ld(x) Stellen repräsentierbar ist). Da die Faktoren aber am Ende in der Größenordnung von 2^n sind, braucht das Shiften O(log(2^n)) = O(n), also mit der äußeren Schleife dann O(n^2). Am Ende einfach 1 abziehen indem die erste (und einzige 1) gesucht und auf 0 gesetzt, und rechts davon alles auf 1 gesetzt wird (hat O(n) und ändert die Laufzeit daher nicht mehr).

Für n^n könnte man im Prinzip dieselbe Lösung nehmen, und dann eine zweite Schleife von 1 bis n^n (mit beliebigem kostanten Body) anhängen um dort die geforderte Laufzeit (sinnlos) zu verbraten. Gewünscht ist aber vermutlich eine intelligentere Lösung wo n^n wirklich beim Rechnen drauf geht. Ich würde 2^n mal die Zahl zu sich selbst addieren (beginnend bei 1 und am Ende 1 abziehen wie oben). Jede Addition hat O(ld(x)) für eine Zahl x, wobei x wieder gegen 2^n strebt, daher O(n). Man braucht für 2^n insgesamt n Additionen mit je einer Laufzeit von n. Also gesamt O(n^n).

(alles modulo Denkfehler meinerseits)

Edit: Wobei man dazu sagen muss dann meine Lösungen eben davon ausgehen dass die Komplexität von Additionen von der Größe der Zahlen abhängt. Das kann man in der Theorie sinnvoller Weise machen (je nachdem wie eure Vorgaben sind), entspricht aber nicht realen Maschinen, wo fixe Datentypen meist eine konstante Laufzeit haben.