Klammerung einer Diskontinuität in einer Schrittfunktion

8

Ich habe die Funktion

f(x)={0(x<a)1/2(x=a)1(x>a) ,

wo unbekannt ist. Ich kann die Funktion für einen beliebigen Wert von Rechen , und versuchen zu bestimmen (bis zu einem gewissen Grad an Genauigkeit).axa

Bei einer anfänglichen Klammer unterteile ich die Klammer durch Definierenx0<a<x1

x2:=x0+x12

und Berechnen von . Dann habe ich entweder oder . Ich konnte mit diesem Ansatz gehen , bis die Bracketing - Werte bis zu einem gewissen Genauigkeit einverstanden ist , und somit für löse .f(x2)x0<a<x2x2<a<x1a

Gibt es einen effizienteren Algorithmus?

user1951162
quelle

Antworten:

7

Nein. Obwohl die Frage in Gleitkomma-Arithmetik formuliert ist, handelt es sich im Kern um eine Frage zur binären Suche. Die binäre Suche ist ein optimaler Algorithmus unter Algorithmen, die auf einem Entscheidungsbaum basieren (z . B. https://stackoverflow.com/q/4571478/491171 ). Alle Lehrbücher für Datenstrukturen und Algorithmen sollten dies diskutieren.

Wenn Sie bei jedem Schritt eine binäre Entscheidung treffen können (ein Vergleich), können Sie intuitiv höchstens eine Information lernen, indem Sie den Suchbereich partitionieren. Das optimale Verhalten besteht immer darin, den Suchbereich in zwei Hälften zu teilen. Wenn einen von Werten annehmen kann , muss die Tiefe eines (binären) Entscheidungsbaums, der mindestens Blätter enthält, sein mindestens . Die binäre Suche erreicht diese Grenze von Schritten. Diese Analyse wendet sowohl das erwartete Verhalten an, wenn alle gleich wahrscheinlich sind, als auch das Worst-Case-Verhalten.an=|highlow|/ϵmachnlog2nlog2na

Wenn Sie einige andere Informationen haben, dann würde es notwendig sein , um genauer zu sein über das, was bedeutet , dass es für „unbekannten“ zu sein, welche Operationen in dem Algorithmus erlaubt sind, und was es bedeutet, „effizienter“ zu sein. (So ​​wie es ist, habe ich sie auf herkömmliche Weise interpretiert.)a

Kirill
quelle
5

Siehe @ Kirills Antwort, aber je nachdem, welche Art von Hardware Sie zur Verfügung haben, können Sie möglicherweise die Parallelität nutzen, um das Problem schneller zu lösen. Angenommen, Sie hatten die Möglichkeit, für Operanden gleichzeitig auszuwerten. Anschließend können Sie Ihre Klammer wiederholt in Intervalle anstelle von . Ob dies tatsächlich "effizienter" oder schneller wäre, ist schwer zu sagen, da es Gemeinkosten und verschiedene Definitionen von Effizienz geben wird.fPP+12

Patrick Sanan
quelle
2
(+1) Aus diesem Grund ist es wichtig, das Berechnungsmodell genau zu definieren, um über die algorithmische Effizienz zu sprechen.
Kirill