上限が不明なときの問題解決法

例えばProblem 60のような条件を満たす最小の解を求る問題を考えます。この問題は条件を満たすような解を小さい順に列挙するのが難しいです。しかし、上限を決めてその範囲で解が存在するかを含めて解くのは比較的簡単です。

このようなときは、適当に上限を決めるとよいです。例えば上限を1000と決めて、その範囲に解が無ければ、上限を2倍にして再び解を求めます。この方法は多くの場合にかなり有効です。上限を決めると問題がぐっと易しくなることはよくあります。また、直接解を求めるより時間がかかりそうですが、致命的にはかかりません。例えば、O(N)の問題のとき、解が8000で、いきなり上限を8000にして解を求めるたとき8秒かかったとします。ことのき、N = 1000から始めて倍々していくと、1 + 2 + 4 + 8 = 15秒かかります。まあ、倍くらいです。最悪の場合、N = 999から始めて倍々していくと、1 + 2 + 4 + 8 + 16 = 31秒と4倍くらいかかります。

しかし、これはいつも有効でしょうか。例えばO(N³)の問題について考えます。すぐにわかりますが、最悪の場合は最善の場合の8倍の時間がかかります。解が8000のとき、N = 1000から倍々して8000のときで終わりますが、N = 999からはじめたときは、7992で終わらずに15984まで計算しなければなりません。このとき約8倍かかることになります。

これを避けるには、倍々ではなくもっと小さい係数を掛けていけばよいでしょう。しかしあまり小さい係数を掛けていては余分な計算をたくさんすることになるでしょう。どこかに最適な係数があるはずです。それを求めます。

定式化します。計算量がO(N^e)、解がM = aⁿ + 1、N = 1から始めてa倍ずつしていきます。そして、a^{n + 1}まで計算するとします。このときの計算量はおおよそ、