Algorithmus zu gegebener Komplexität

[Troubles]

Hallo,

Ich hoffe, ich poste hier unter dem richtigen Thema.

Die Aufgabenstellung lautet: Konstruieren sie für die folgende asymptotische Laufzeitkomplexität einen möglichst einfachen Algorithmus:

O(n)=Sqrt[n]

Versuchen Sie, die Komplexität durch geeignete Schachtelung von Schleifen zu erreichen.

Wie erreiche ich so ein Laufzeitverhalten?
Hat irgendjemand eine Idee? Ich hab nicht mal eine sinnvolle Lösungsidee zu diesem Problem gefunden 🙁

 

[s4ke]

Mir fällt was richtig blödes dazu ein, ich hoffe das passt auch (aber nur mit einer Schleife?)

Wieso nicht einfach eine Bruteforce Methode bauen, die nur bis sqrt(n) in einer for() Schleife läuft. Aber mit Schachtelung hat das leider nichts zu tun.

 

[Troubles]

Oh hallo,

wir dürfen leider nur Schleifen und Verzweigungen verwenden.
Eine quadratishe Laufzeit O(n^2) erreicht man beispielsweise durch 2 for-Schleifen:
for (int i=0; i<n;i++){
for (int j=0; j<i;j++){}

}

Ich habe mal versucht mit mathematica die Funktion darzustellen; für kleine n schaut die kurve der Funktion f=log10[n]^3 ahnlich aus, für große n stimmts dann leider gar nicht mehr. Ich bin mit meiner Weisheit bei diesem bsp. am Ende.

 

[Kruemel]

Der Test auf Primzahlen ist zb. ein Algorithmus der Komplexität sqrt(n). Alle Werte größer als sqrt(n) kommen nicht in Frage.

Das ist aber eine einzige Schleife.

Gruß, Kruemel

Edit: Müsste in der inneren Schleife deines Beispiels nicht auch bis n iteriert werden damit n² rauskommt?

Edit 2: Totaler Käse das mit den Primzahlen, ich nehm alles zurück... oO

 

[Marco13]

Irgendwie habe ich die dumpfe Vermutung, dass man nicht einfach die Grenze "sqrt(n)" in der for-Schleife angeben soll. Sonst wären solche Aufgaben ... nun, nicht soooo anspruchsvoll:
O(n) : for (int i=0; i<n; i++) {}
O(n^2) : for (int i=0; i<n*n; i++) {}
O(sqrt(n)) : for (int i=0; i<sqrt(n); i++) {}
O(log(n)) : for (int i=0; i<log(n); i++) {}
...
Aber spontan könnte ich keinen (in diesem Sinne "nicht-trivalen") O(sqrt(n))-Algorithmus nennen :bahnhof: Wenn schon, dann vielleicht irgendwie versteckt...
int x = 0;
int y = 0;
while (x<n) { x+=y; y++ }
oder so... (kommt das hin? ... muss mal einer formal nachprüfen....)

 

[sdkjfndsaf]

Welche Laufzeit hat denn diese Schleife hier?

for (int i = 0; i*i*i < n; i++) {}

 

[Marco13]

O(cbrt(n)), "Cube Root", "Dritte Wurzel", natürlich könnte man
for (int i=0; i*i<n; i++)
für die sqrt-Sache schreiben, aber das kommt ja auf's gleiche raus, wie die Beispiele, die ich gepostet hatte....

 

[Troubles]

Hallo Leute,

sry für meine längere Abwesenheit, hatte etwas Lernstress in den letzten Tagen.
Ich bin im www auf eine Seite gestoßen, in der einige bsp. zur Komplexität angegeben sind:

¨Ubungen zu Algorithmen

unter Page 2 ist ein Algorithmus angegeben welcher ein Quadratwurzel-Laufzeitverhalten hat.
Kennt diesen Algorithmus irgendjemand?