Suche in unendlicher Menge |
| 17.11.2014, 20:04 | Auf diesen Beitrag antworten » | ||||
| riemansson | 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? |
||||
|
|
|||||
| 18.11.2014, 07:16 | Auf diesen Beitrag antworten » | ||||
| eulerscheZahl | 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. |
||||
| 13.01.2015, 00:17 | Auf diesen Beitrag antworten » | ||||
| ed209 | 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, 01:02 | Auf diesen Beitrag antworten » | ||||
| Karlito | 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 |
||||
| Anzeige | |||||
|
|
|||||
| 18.01.2015, 16:24 | Auf diesen Beitrag antworten » | ||||
| ed209 |
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 |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
| Die Neuesten » |
|
