この単調な非線形傾向でlogn検索のパフォーマンスよりも優れた結果が得られますか？

Question

私の問題

（あなたはこれをスキップして、実際の質問については、次のセクションに行くことができます。これは本当に知りたい人のためだけの背景情報である「なぜ一体あなたはこれを求めている？」）

摩擦のない丘を滑り降りる物体を想像してください。加速が0のフラットエリアがあり、残りのパスは0より大きい9.81 m/s^2までの加速度を持ちます。あなたが丘の形状を知っているなら、丘の下の位置の関数として最大加速度をプロットすることができます。別の惑星や月に同じ丘を置き、異なった見た目の加速と位置プロファイルを得るとしましょう。どうして？目標は正確な加速度を選択して、ちょうど10秒で丘の底に達するようにすることです。あなたのポジションの変更は修正されました。正確に10秒で丘を下っている限り、最初の速度は0で、最終的な速度は無関係です。丘の表面との接触を失うことは決してないと仮定してください。

これは、あなたが加速値（惑星を変更する）を差し込み、10秒の下り坂の移動後に位置を取得できることを意味します。この関係をプロットすると、単調に増加するプロットが得られます（x軸の加速度が高いほど、y軸上の10秒の位置変化値が高くなります）。しかし、私の丘は非常に複雑です。私は、関係が3乗または2乗であると仮定することはできません。しかし単調に増加しています。ここで

は私のアルゴリズムからのプロットを持ついくつかのサンプルデータです：

acc = [ 
1.5000 2.0000 2.5000 3.0000 3.5000 4.0000 4.5000 
5.0000 5.5000 6.0000 6.5000 7.0000 7.5000 8.0000 
8.5000 9.0000 9.5000 10.0000 10.5000 11.0000 11.5000 
12.0000 12.5000 13.0000 13.5000 14.0000 14.5000 15.0000 
15.5000 16.0000 16.5000 17.0000 17.5000 18.0000 18.5000 
] 

pos = [ 
5.9176 6.5810 6.9784 7.2429 7.4314 7.5725 7.6818 
7.7691 7.8402 7.8992 7.9489 7.9913 8.0279 8.0597 
8.0877 8.1123 8.1342 8.1538 8.1714 8.1872 8.2016 
8.2146 8.2265 8.2374 8.2472 8.2550 8.2617 8.2676 
8.2676 8.2676 8.2676 8.2676 8.2676 8.2676 8.2676 
] 

もちろん、私はMATLABを使用しています、しかし、これは言語に依存しないです。私のデータは、私が上記で説明した問題とは若干異なる現在のアルゴリズムからのものであることに注意してください。

通報一般

非線形及び非線形化可能な傾向に伴って単調に増加または減少する関数が与えられると、検索補間検索（loglogn）と同様のアルゴリズム、又は少なくとも良好ですバイナリ/ゴールドセクション検索（logn）より適切な入力を見つけることができますか？

私の直感は、単調で傾向があるので、lognよりも優れたものがあるはずです。私は、トレンド・アイは使い方が良いとは言いませんが、私が言うことを伝えていると思います。

NOTES：

1. それはxからそのAY計算を知るために役立つことは、計算上、非常に高価である

UPDATE

私はLOGNより良いを達成することができませんでしたのこの特定の傾向の線形化なしのパフォーマンス。データは加速度値を反転することによって線形化可能であるが、@Gassaによって提案されたNewton-Raphson型アプローチは、関数の導関数の計算上高価な/不可能な計算のために成功しなかった。

残念ながら、これは不可能かどうかの疑問に答えるものではありません。 fとf 'に対する高価な計算時間を伴う単調な傾向のloglogn探索アルゴリズムを見つけることが可能であるかもしれない。この質問には数学的証明が必要です。おそらく、この質問を数学のスタック交換サイトに持ってくる時間です。

@Penguinoの答えの貢献が私が補間検索を使用できるようにデータを線形化する方法につながったと私は信じています。このため、彼の答えは正しいとマークされています。

Answer 1

は、だから私は理解していれば、あなたは単調に2つの制限X0とX1、およびそれらの限界の間のすべてのxについてもゼロより大きい間で増加している関数A（X）を持っています。そして、あなたのオブジェクトはx0とx1の間の加速度k.A（x）を経験します。ここで、kは局所的な重力に関連する倍率です。また、時間t0 = 0、位置x0で速度v0 = 0で開始し、時間t1 = 10で位置x1で終了するには、スケーリング係数kを適切に選択します。

この場合、私は旅行の時間は1/sqrt（k）に比例すると信じています。だから、あなたがする必要があるのは正確に正確に移動時間を正確に計算することです。いくつかの任意のkに対して、適切な縮尺をします。たとえば、k = 1の旅行時間がT1の場合、k =（T1）^ 2/100の旅行時間は10秒になります。

ので、所要時間はOである（？）旅行時間の単一の正確な計算を行うために必要な（おそらくいくつかの区分的数値積分はそのためだろう）。