N個の点をn個の区間に入れるのに最も良いアルゴリズムは何ですか

Question

区間[0,1]にN個の点があり、この区間をn個の部分区間に分割したとしましょう。[0、 [xn-1]、[xn-1,1]次に、これらのN点のそれぞれがどのサブ間隔に属するのかを判断する必要があります。この仕事を完了するための最良のアルゴリズムは何ですか？これらのサブ間隔は均等に分配されないが、それらは既知である。 NはO（100万）、nはO（1 k）です。

Answer 1

IFポイントがソートされていない場合は、座標で並べ替えます。

間隔リストを持つポイントリストのマージ（MergeSortのマージアルゴリズムなど）を実行します。 （両方のリストがすでにソートされている場合やO(N + n)）

複雑さはO(NlogN + N + n)ある

@Mukul Varshneyのアプローチの複雑O(Nlogn)と比較して、あなたのケース

Answer 2

各区間の下限を0とすると、x1、x2、x3 ....の順番で配列の区間の最初の値（下限）を保持し、バイナリ検索を使用してインデックスnの数よりも多いか少ない。