範囲 LCM クエリ用の JavaScript プログラム

LCM は最小公倍数の略で、数値セットの最小公倍数は、指定されたセットに存在するすべての数値で割り切れるすべての数値の中で最小の数値です。特定の問題の説明とともに完全なコードを確認します。この記事では、一連の LCM クエリ用の JavaScript プログラムを実装します。

問題の紹介

この問題では、整数を含む配列と、指定された配列範囲を表す数値のペアを含む別の配列クエリが与えられ、その指定された範囲内のすべての要素の最小公倍数を計算する必要があります。例えば ​​-＃＃＃

指定された配列が [1, 2, 3, 4, 5, 6] で、クエリ配列が [[1,3], [2,5]] の場合、最初のクエリ要素は [2] になります。 、3、4]および12はLCMです。

2 番目のクエリ要素が [3, 4, 5, 6] の場合、LCM は 60 です。

LCM と GCD の数学的関係

GCD を求めるには、対数複雑度の 2 つの数値の GCD を見つけることができるユークリッドの公式があり、LCM と GCD の間にはこのような関係があります -

リーリー

つまり、すべての数値の GCD と積を求め、そこから O(1) 演算でその数値の最小公倍数を求めることができます。

単純な方法

最も簡単な方法は、クエリの配列を反復処理し、各クエリの指定された範囲内の要素と GCD の積を見つけることです。これら 2 つの値から LCM を見つけて返します。コードで実装しましょう -

＃＃＃例＃＃＃ リーリー

時間と空間の複雑さ

上記のコードの時間計算量は O(Q*N*log(D)) です。ここで、Q はクエリの数、N は配列内の要素の数、D は存在する配列の最大数です。配列内で。

余分なスペースを使用していないため、上記のコードのスペース複雑さは O(1) です。

上記のプログラムでは、クエリの数が N に等しい場合、その時間計算量は N

2

より大きくなり、この方法は非効率的になります。これが別の方法であることを見てみましょう &miinus;

^{線分ツリー法}

線分ツリーは、問題を複数の線分に分割し、それらを 2 のべき乗形式で接続するために使用される高レベルのデータ構造です。これには範囲クエリ用にある程度のスペースが必要で、結果は対数時間で生成されます。コードを見てみましょう -

＃＃＃例＃＃＃ リーリー ＃＃＃結論は＃＃＃

このチュートリアルでは、範囲 lcm クエリを見つけるための JavaScript 記事を実装しました。 2 つの方法を見てきました。1 つは時間計算量 O(Q*N*log(D)) の単純な方法であり、もう 1 つは時間計算量 O(Q*log(N)) の線分ツリーです。

以上が範囲 LCM クエリ用の JavaScript プログラムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。