 Suche in unendlicher Menge |
riemansson
Grünschnabel
Dabei seit: 04.11.2013
Beiträge: 3
 |
|
| 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?
|
|
17.11.2014 20:04 |
|
|
|
|
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.
__________________
Syntax Highlighting fürs Board (Link)
|
|
|
18.11.2014 07:16 |
|
|
ed209
Routinier
Dabei seit: 07.09.2006
Beiträge: 324
|
|
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
|
|
|
13.01.2015 00:17 |
|
|
Karlito 
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
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
|
|
|
13.01.2015 01:02 |
|
|
ed209
Routinier
Dabei seit: 07.09.2006
Beiträge: 324
|
|
| 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
|
|
|
18.01.2015 16:24 |
|
|
|
