---

Geschrieben von riemansson am 17.11.2014 um 20:04:

  Suche in unendlicher Menge

Hallo zusammen,

mich beschäftig gerade folgende Frage: Wie schnell kann man in einer unendliche Menge suchen? Ich würde sagen O(n), indem ich alle Möglichkeiten durchprobiere.
Mal ein Beispiel: ich will eine geheime Zahl aus den natürlichen Zahlen erraten. Ich bekomme nur die Antwort ob ich drunter bin oder ob ich richtig bin.
Ich würde jetzt mit 1 anfangen dann 2 usw....(ziemlich einfach aber ich finde nix was wirklich besser wär).
Auch wenn ich irgendwie anders testen würde (bspw. in 2er Schritten oder verdoppeln würde), dann gibt es doch immer worstcases, in denen ich ewig Zeit brauche.

Hat vllt. jemand einen Ansatz?

---

Geschrieben von eulerscheZahl am 18.11.2014 um 07:16:

 

Das Optimum ist O(log(n)).
Du prüfst immer die Mitte des Intervalls auf größer/kleiner, damit halberst du die Menge in jedem Schritt.
Wenn du so einen Eintrag in einer Liste finden willst, muss die Liste sortiert sein.
Stichwort für weitere Recherche: binäre Suche.

---

Geschrieben von ed209 am 13.01.2015 um 00:17:

 

Ich glaube die Frage lässt sich nicht wirklich beantworten.
Um die Komplexität einer Berechnung anzugeben, braucht man eine Eingabe und eine Ausgabe.
Was ist in deinem Fall die Eingabe? Eine Liste aller möglichen natürlichen Zahlen? Die Zahl die du suchst?

Ich fürchte deine Problemstellung ist nicht klar definiert und/oder lässt sich mit klassischer Komplexitätstheorie nicht beantworten.

Gruß,
ED

---

Geschrieben von Karlito am 13.01.2015 um 01:02:

 

Hey @ed, schön dich mal wieder hier zu sehen!

ich tippe mal euler hat recht. Diskussionsgrundlage: Man nehme eine beliebige gesuchte Zahl (die Eingabegröße), welche in einer abzählbar unendlichen menge Enthalten ist (für überabzählbare Mengen ist das Problem nicht Lösbar). Ich verdopple so lange meine Probezahl, bis sie größer ist, als die gesuchte. Nennen wir die Probezahl x. Danach habe ich ein Intervall von x/2 bis x in dem ich nach der gesuchten Zahl suchen muss. Mit binärer Suche habe ich ich dann eine Komplexität von O(log(n)). Über den Daumen ist die Laufzeit, bis ich die gesuchte Zahl gefunden habe auch O(log(n)). Somit habe ich eine Gesamtkomplexität von O(2log(n)) = O(log(n))...

Habe ich etwas übersehen?

Gruß,

Karlito

---

Geschrieben von ed209 am 18.01.2015 um 16:24:

 

Zitat:

Zitat:

Habe ich etwas übersehen?

Allerdings
Die Eingabegröße n entspricht nicht dem Wert der Eingabe, sonderer der Länge der eingabe.
Wenn wir also die Zahl k suchen ist n = log k.
Anstelle von O(n) = log n erhältst du O (log k) = log k oder O (n) = n
Sehen wir die Eingabe als bitstream der mit einem blank terminiert ist, ist die implementation deines Algorithmus als Turingmaschine übrigens trivial:

t(q0, 0) = (q0, 0, R)
t(q0, 1) = (q0, 1, R)
t(q0, B) = (HALT)

Oder mit anderen Worten du gibst deine Eingabe aus. Immerhin ist die Aufgabe nichts anderes als f(k) = k zu berechnen.

Ich bleib dabei: Die Aufgabe irgendetwas in den natürlichen Zahlen zu finden ist nicht wirklich klar definiert. Schließlich ist eine natürliche Zahl nichts was einem so einfach abhanden kommt.

Gruß,
ED