この問題は、与えられた範囲内で機能f(x)=n%x
の最大値を見つけることと等価です。のは、この機能がどのようなものか見てみましょう:
それは我々がx=k
で始まり、それが(x=max+1
まで)どんな意味がありますしながらx
を減少させる場合、我々はすぐに最大値を得ることができることは明らかです。また、この図は、x
がsqrt(n)
より大きい場合、x
を順次減らす必要はないことを示しています。代わりに直前のローカル最大値に直ちにジャンプできます。
int maxmod(const int n, int k)
{
int max = 0;
while (k > max + 1 && k > 4.0 * std::sqrt(n))
{
max = std::max(max, n % k);
k = std::min(k - 1, 1 + n/(1 + n/k));
}
for (; k > max + 1; --k)
max = std::max(max, n % k);
return max;
}
マジック定数4.0
最初の(高価な)ループの反復回数を減少させることによってパフォーマンスを改善することを可能にします。
最悪の時間の複雑さは、O(min(k、sqrt(n)))と見積もることができます。しかし、十分に大きい場合、k
はこの見積もりはおそらくあまりにも悲観的です:我々はずっと早く最大値を見つけることができ、k
がsqrt(n)
よりかなり大きい場合、それを見つけるのに1回または2回の反復しか必要ありません。
私はn
の異なる値のため、最悪の場合には必要とされている反復回数を決定するためにいくつかのテストをした:
n max.iterations (both/loop1/loop2)
10^1..10^2 11 2 11
10^2..10^3 20 3 20
10^3..10^4 42 5 42
10^4..10^5 94 11 94
10^5..10^6 196 23 196
up to 10^7 379 43 379
up to 10^8 722 83 722
up to 10^9 1269 157 1269
成長率は、O(SQRT(N))よりも著しく優れています。
"k"の高い値から検索を開始すると、検索が短絡する可能性があります。私はそれがbig-oに影響するとは思わない。 –
この質問は、http://math.stackexchange.com/ IMOにはるかに適しています。手元の主な問題は、プログラム的ではなくアルゴリズム的な問題です。 –
@barakmanos。 。 。それは言うのは難しいです。 OPは問題の解決方法を知っていますが、効率的な実装を探しています。 –