6

配列が与えられた場合a[]、少なくとも 1 つの要素iが条件を満たしているかどうかを判断する最も効率的な方法は何でしょうa[i] == iか?

配列内のすべての要素はソートされ、区別されますが、必ずしも整数型であるとは限りません (つまり、浮動小数点型である可能性があります)。

4

6 に答える 6

8

「ソートされた」、「異なる」、「必ずしも整数ではない」の関連性について、何人かの人々が主張しています。実際、この問題を解決するための効率的なアルゴリズムの適切な選択は、これらの特性に依存します。配列内の値が個別で整数であることがわかった場合は、より効率的なアルゴリズムが可能になりますが、値が整数であるかどうかに関係なく、値が非個別である可能性がある場合は、効率の低いアルゴリズムが必要になります。そしてもちろん、配列がまだ並べ替えられていない場合は、最初に並べ替えてから（平均複雑度O（n log n））、より効率的な事前並べ替えアルゴリズム（つまり、並べ替えられた配列の場合）を使用できますが、並べ替えられていません。配列をソートせずにそのままにして、線形時間（O（n））の値を直接比較する方が効率的です。選択したアルゴリズムに関係なく、最良のパフォーマンスはO（1）であることに注意してください（調べた最初の要素にそのインデックス値が含まれている場合）。アルゴリズムの実行中の任意の時点で、次のような要素に遭遇する可能性があります。a[i] == iその時点でtrueを返します。この問題でアルゴリズムのパフォーマンスに関して実際に重要なのは、すべての要素をどれだけ迅速に除外し、そのような要素がないことを宣言できるかということa[i]ですa[i] == i。

この問題では、のソート順は示されていませんa[]。これは、欠落している情報の非常に重要な部分です。昇順の場合、最悪の場合の複雑さは常にO（n）になり、最悪の場合の複雑さを改善するためにできることは何もありません。ただし、並べ替え順序が降順の場合、最悪の場合の複雑さもO（log n）です。配列内の値は明確で降順であるため、にa[i]等しい可能性のあるインデックスは1つだけiであり、基本的には、クロスオーバーポイント（このようなクロスオーバーがある場合でも、昇順のインデックス値が降順の要素値と交差する場所）を見つけ、クロスオーバーポイントのインデックス値であるかどうかを判断するためのバイナリa[c] == c検索c。それはかなり些細なことなので、ソート順が昇順であると仮定して続行します。興味深いことに、要素が整数の場合、昇順の場合でも同様の「クロスオーバーのような」状況があります（ただし、昇順の場合は複数のa[i] == i一致が存在する可能性があります）。したがって、要素が整数の場合、バイナリ検索も次のようになります。昇順の場合に適用できます。この場合、最悪の場合のパフォーマンスでさえO（log n）になります（インタビューの質問-ソートされた配列XでX [i] = iとなるようなインデックスiを検索するを参照）。しかし、このバージョンの問題では、そのような贅沢は与えられていません。

この問題を解決する方法は次のとおりです。

最初の要素であるa[0]。その値が== 0、の場合、次の条件を満たす要素が見つかりましたa[i] == i。trueを返します。その値が< 1、の場合、次の要素（a[1]）に値が含まれている可能性がある1ため、次のインデックスに進みます。ただし、a[0] >= 1（値が異なるために）条件a[1] == 1が真になる可能性がないことがわかっている場合は、インデックスを安全にスキップできます1。ただし、それよりも優れた方法を実行することもできます。たとえば、の場合a[0] == 12、（値は昇順で並べ替えられているため）要素のa[i] == i前に満たす要素は存在しない可能性があることがわかります。a[13]。配列内の値は非整数である可能性があるため、この時点でこれ以上の仮定を行うことはできません。したがって、直接スキップしても安全な次の要素は次のとおりです（a[13]たとえばa[1]、スルーには、とa[12]の間の値が含まれている可能性があります。確認する必要があります）。12.000...13.000...a[13]13

このプロセスを続行すると、次のようなアルゴリズムが生成されます。

// Algorithm 1
bool algorithm1(double* a, size_t len)
{
    for (size_t i=0; i<len; ++i) // worst case is O(n)
    {
        if (a[i] == i)
            return true; // of course we could also return i here (as an int)...
        if (a[i] > i)
            i = static_cast<size_t>(std::floor(a[i]));
    }
    return false; // ......in which case we’d want to return -1 here (an int)
}

a[]これは、の値の多くがインデックス値よりも大きい場合はかなり良好なパフォーマンスを示し、のすべての値a[]がnより大きい場合は優れたパフォーマンスを示します（1回の反復でfalseを返します）が、すべての値がインデックス値よりも小さい（n回の反復後にfalseを返します）。それで、製図板に戻ります...しかし、必要なのはわずかな調整だけです。アルゴリズムは、0からnまで順方向にスキャンするのと同じくらい簡単に、nから0まで逆方向にスキャンするように作成できたと考えてください。両端から中央に向かって反復するロジックを組み合わせると、次のようなアルゴリズムが得られます。

// Algorithm 2
bool algorithm2(double* a, size_t len)
{
    for (size_t i=0, j=len-1; i<j; ++i,--j) // worst case is still O(n)
    {
        if (a[i]==i || a[j]==j)
            return true;
        if (a[i] > i)
            i = static_cast<size_t>(std::floor(a[i]));
        if (a[j] < j)
            j = static_cast<size_t>(std::ceil(a[j]));
    }
    return false;
}

これは、両方の極端な場合（すべての値が0未満またはnより大きい）で優れたパフォーマンスを発揮し、他のほとんどの値の分布でかなり優れたパフォーマンスを発揮します。最悪のケースは、配列の下半分のすべての値がインデックスより小さく、上半分のすべての値がインデックスより大きい場合です。この場合、パフォーマンスは最悪の場合のO（ n）。最良のケース（どちらかの極端なケース）はO（1）であり、平均的なケースはおそらくO（log n）ですが、確実にそれを決定するために数学専攻の人に任せています。

何人かの人々は、問題をどのように分割できるか、そして再帰的に分割されたサブ問題で何をするかを指定せずに、問題への「分割統治」アプローチを提案しました。もちろん、そのような不完全な答えはおそらくインタビュアーを満足させないでしょう。ナイーブ線形アルゴリズムと上記のアルゴリズム2の最悪の場合のパフォーマンスは両方ともO（n）ですが、アルゴリズム2は、可能な限り要素をスキップ（検査しない）することにより、平均ケースのパフォーマンスを（おそらく）O（log n）に改善します。分割統治法は、平均的な場合、アルゴリズム2がスキップできるよりも多くの要素をスキップできる場合にのみ、アルゴリズム2を上回ることができます。配列を2つの（ほぼ）等しい連続した半分に再帰的に分割することによって問題を分割し、結果として生じるサブ問題で、特にアルゴリズム2の最悪の場合、アルゴリズム2がスキップできるよりも多くの要素をスキップできる可能性があります。この説明の残りの部分では、アルゴリズム2の最悪のケースとなる入力を想定します。最初の分割後、O（1）のパフォーマンスをもたらす同じ極端なケースについて、両方の半分の上部と下部の要素をチェックできます。アルゴリズム2ですが、両方の半分を組み合わせた場合、O（n）のパフォーマンスが得られます。これは、下半分のすべての要素が0未満で、上半分のすべての要素がn-1より大きい場合に当てはまります。このような場合、除外できる半分のO（1）パフォーマンスを使用して、下半分および/または上半分をすぐに除外できます。もちろん、そのテストで除外できない半分のパフォーマンスは、さらに繰り返した後、まだ決定されていません。上または下の要素にインデックス値が含まれているセグメントが見つかるまで、その半分をもう一度半分に分割します。これは、アルゴリズム2に比べてかなり優れたパフォーマンスの向上ですが、アルゴリズム2の最悪のケースの特定の特殊なケースでのみ発生します。分割統治で行ったのは、最悪の場合の動作を引き起こす問題空間の割合を（わずかに）減らすことだけです。分割統治の最悪のシナリオはまだあり、アルゴリズム2の最悪の動作を引き起こす問題空間のほとんどと完全に一致します。分割統治で行ったのは、最悪の場合の動作を引き起こす問題空間の割合を（わずかに）減らすことだけです。分割統治の最悪のシナリオはまだあり、アルゴリズム2の最悪の動作を引き起こす問題空間のほとんどと完全に一致します。分割統治で行ったのは、最悪の場合の動作を引き起こす問題空間の割合を（わずかに）減らすことだけです。分割統治の最悪のシナリオはまだあり、アルゴリズム2の最悪の動作を引き起こす問題空間のほとんどと完全に一致します。

したがって、分割統治アルゴリズムには最悪のシナリオが少ないことを考えると、先に進んで分割統治アプローチを使用することは理にかなっていますか？

一言で言えば、いいえ。まあ、多分。データの約半分が0未満で、半分がnより大きいことを事前に知っている場合、この特殊なケースは、一般に分割統治法の方がうまくいくでしょう。または、システムがマルチコアで「n」が大きい場合は、問題をすべてのコア間で均等に分割すると役立つ場合がありますが、コア間で分割された後は、各コアのサブ問題がおそらく最良であると私は主張します。上記のアルゴリズム2で解決し、問題のさらなる分割を回避し、以下で議論するように、確実に再帰を回避します。

再帰的な分割統治アプローチの各再帰レベルで、アルゴリズムは、問題の前半に再帰する間、問題のまだ解決されていない後半を記憶するための何らかの方法を必要とします。多くの場合、これは、アルゴリズムが最初に半分を再帰的に呼び出し、次にもう一方を再帰的に呼び出すことによって行われます。これは、この情報をランタイムスタックに暗黙的に保持する設計です。別の実装では、基本的にこれと同じ情報を明示的なスタックに保持することで、再帰的な関数呼び出しを回避できます。スペースの拡大に関しては、アルゴリズム2はO（1）ですが、この情報をある種のスタックに保持する必要があるため、再帰的な実装は不可避的にO（log n）になります。しかし、スペースの問題は別として、再帰的な実装には、再帰できるようになるまで、サブ問題の半分にまだ再帰されていない状態を記憶するという追加の実行時オーバーヘッドがあります。この実行時のオーバーヘッドは無料ではありません。上記のアルゴリズム2の実装が単純であることを考えると、このようなオーバーヘッドは比例して重要であると思います。したがって、上記のアルゴリズム2は、ほとんどの場合、再帰的な実装に丸みを帯びることをお勧めします。

于 2012-12-01T23:27:46.713 に答える
4

最悪の場合、すべての要素をチェックするよりも良い方法はありません。（のようなものを想像してみてくださいa[i] = i + uniform_random(-.25, .25)。）入力がどのように見えるかについての情報が必要になります。

于 2012-11-29T19:15:01.617 に答える
1

実際には、最後の要素から始めて、基本的なチェックを行います (たとえば、1000 個の要素があり、最大が 100 の場合、チェックする必要があるのは 0..100 だけです)。最悪のシナリオでも、すべての要素をチェックする必要がありますが、可能性のある領域を見つける方が速くなるはずです。上記のように (a[i] = i + [-0.25..0.25]) の場合、f($!ed であり、すべての要素を検索する必要があります。

于 2012-11-29T20:10:50.053 に答える
0

ここでの主な問題は、矛盾するステートメントだと思います。

a [i] == i

配列内のすべての要素はソートされて区別されます。常に整数である必要はありません。

配列の値がアクセスする添え字と等しい場合、それは整数であることを意味します。それが整数ではなく、彼らが言うなら.. char、何が「ソートされた」と見なされますか？ASCII値（A < B < C）？

それが文字の配列である場合、次のことを考慮します。

a[i] == i

本当なら

i == 65 10 && a [i] =='A'

もし私がこのインタビューに参加していたら、私は答える前にフォローアップの質問でインタビュアーを焼きます。そうは言っても...

あなたが述べたことだけがわかっている場合は、O（n）で値を見つけることができると言っても過言ではありません。これは、配列を1回フルパスするときだからです。詳細については、配列の二分探索を使用して、これをO（log（n））に制限できます。

于 2012-11-29T19:58:00.210 に答える
0

ソートされた配列の場合、補間検索を実行できます。二分探索に似ていますが、値が均等に分布していると仮定すると、より高速になる可能性があります。

于 2012-11-29T19:07:54.247 に答える
0

配列内のすべての要素がソートされ、個別であることに注意してください。したがって、新しい配列 b を b[i]=a[i]-i で構築すると、配列 b の要素もソートされます。見つける必要があるのは、配列 b のゼロ。二分探索で問題を解決できると思います！これは、ソートされた配列の出現回数をカウントするためのリンクです。補助配列を構築せずに、元の配列に対して同様の分割統治法を実行することもできます。時間計算量は O(Logn) です!

Take this as an example:
a=[0,1,2,4,8]
b=[0,0,0,1,4]
What we need to find is exactly index 0,1,2

それが役に立てば幸い！

于 2012-12-01T07:12:50.790 に答える