私はすでにこの投稿を読みましたが、答えは私を満足させませんでした配列がLog（N）でソートされているかどうかを確認してください。
1,000,000を超える深刻な大きな配列double（正および/または負）があり、doubleとfloatの比較に時間がかかりすぎるため、比較の最大数を回避しようとして配列が「ソート」されているかどうかを知りたいとします。それに関する統計を使用することは可能ですか？そしてそれがあった場合：
"the array sorted"か？ありがとう。
それはあなたの要件に依存します。1.000.000から100個のランダムサンプルで十分であると言えば、それがソートされていると仮定します-そうです。しかし、絶対に確実にするために、あなたは常にすべてのエントリを通過する必要があります。この質問に答えることができるのはあなただけです。なぜなら、それがソートされていることについてどれだけ確実である必要があるかを知っているのはあなただけだからです。
配列がソートされているかどうかを判断するための比較の最大数はN-1です。これは、比較する隣接する数値のペアがN-1個あるためです。しかし、簡単にするために、NまたはN + 1の数を見ても問題ではないので、Nと言います。
さらに、どこから始めるかは重要ではないので、最初から始めましょう。比較＃1（A[0]とA[1]）。失敗した場合、配列はソートされていません。それが成功すれば、良いです。
比較するだけなので、これを隣人に減らし、左側のものが小さいか等しいか（1）、そうでないか（0）を減らすことができます。したがって、配列を0と1のシーケンスとして扱うことができ、2つの隣接する数値が順番に並んでいるかどうかを示します。
エラー率または妥当性（正しいスペル？）を計算するには、0/1シーケンスのすべての組み合わせを調べる必要があります。私はそれを次のように見ます：配列の2 ^ nの組み合わせがあります（つまり、ペアの順序で、そのうちの1つだけがソートされます（すべての要素は1であり、各A[i]がA[以下であることを示します）。 i + 1]）。
これは単純なようです。最初はエラーは1/2^Nです。最初の比較の後、可能な組み合わせの半分（すべてソートされていない）が削除されます。したがって、エラー率は1/2 ^ n + 1/2 ^（n-1）である必要があります。
私は数学者ではありませんが、エラー率に到達するために必要な要素の数を計算するのは非常に簡単です（ERROR> = 1/2 ^ n + 1/2 ^（n-1）の合計となるようなxを見つけます... 1 / ^（2-x））
紛らわしい英語でごめんなさい。私はドイツから来ました。
マルチプロセッシング（実際の並列処理、つまりマルチコアCPUの場合のみ）を使用して分割統治アルゴリズムを実行すると、Log（N）で配列が並べ替えられているかどうかを確認できます。
GPUマルチプロセッシングを使用している場合、最新のグラフィックカードは数千のプロセスを並行して実行できるため、Log（N）を非常に簡単に実現できます。
あなたの質問5は、他の答えを決定するために答える必要がある質問です。配列が完全にソートされていることを確認するには、すべての要素を調べる必要があります。これらの要素のいずれかが適切でない可能性があるためです。
これは高校で教えられている古典的な確率の問題です。この質問を検討してください：
バッチが拒否される確率はどれくらいですか？8,000のバッチでは、7％の時計に欠陥があります。8,000から10（置換なし）のランダムサンプルが選択され、テストされます。少なくとも1つに欠陥がある場合、バッチ全体が拒否されます。
したがって、大きな配列からいくつかのランダムなサンプルを取得して、それが並べ替えられているかどうかを確認できますが、サンプルが故障している可能性を知る必要があることに注意する必要があります。あなたはその情報を持っていないので、確率論的アプローチはここでは効率的に機能しません。
（ただし、配列の50％をチェックして、正しくソートされる可能性が50％あると素朴に結論付けることができます。）
すべての単一要素がオフラインの1つの要素になる可能性があるため、すべての要素を実行する必要があります。したがって、アルゴリズムには実行時O（n）があります。
「ソート済み」の理解がそれほど厳密でない場合は、「ソート済み」が何を意味するのかを指定する必要があります。通常、「ソート済み」とは、隣接する要素が多かれ少なかれ等しい条件を満たすことを意味します。
他の誰もが言うように、それがソートされていることを100％確実にする唯一の方法は、すべての要素、つまりO（N）を実行することです。
ただし、並べ替えが心配な場合は、配列要素をメモリの連続部分に格納するよりも、最初に並べ替えることの方が重要だと思います。
私が得ているのは、定義上、要素が厳密な弱順序に従うマップを使用できるということです。つまり、マップ内の要素は常に並べ替えられます。セットを使用して同じ効果を達成することもできます。
例：std::map<int,double> collectoin;配列のようにほぼ使用できるようになります：collection[0]=3.0; std::cout<<collection[0]<<std:;endl;。もちろん違いはありますが、並べ替えが非常に重要な場合は、データを格納するために配列を選択するのは間違っています。
昔ながらのやり方です。印刷して、順番にあるかどうかを確認してください。本当にあなたのソートが間違っているなら、あなたはおそらくすぐにそれを見るでしょう。100以上のもののように並べ替えている場合、わずかな順序の誤りしか見られない可能性が高くなります。私がそれに対処するときはいつでも、私のすべてが完全にオフになっているか、それが機能しています。
おそらく使用すべきではないが、サンプリングサイズを示す例として：
統計的に有効なサンプルサイズは、ソートの妥当な推定値を提供します。95％確実にすべてがソートされるようにしたい場合は、サンプリングする真にランダムなポイントのリストを作成することでそれを行うことができます（おそらく〜1500）。
値のリストが1つの場所で乱れていると、後続のアルゴリズムやデータ要件が破られる場合、これは本質的にまったく無意味です。
これが問題になる場合は、コードを実行する前にリストを前処理するか、コードで非常に高速なソートパッケージを使用してください。ほとんどの並べ替えパッケージには検証モードもあります。このモードでは、リストが並べ替えの基準を満たしているかどうかを確認できます。チェックをスレッドと並列化するなどの他の提案は素晴らしいアイデアです。