algorithm - 指定された配列内の負の数を決定する高速アルゴリズム

Question

配列に負の数が1つしかない場合、特定の配列で負の数を見つけるより迅速な方法があるかどうかを提案してください。ソートはオプションだと思いますが、もっと早い方法があれば助かります。

Answer 1

並べ替えは、配列のすべての要素を調べるよりも速くはありません (並べ替えるには、それも行う必要があるため)。

可能な限り最速の方法は、すべての配列を調べて、負の数を 1 つ検出したら停止することです。

Answer 2

配列をトラバースするだけです。それがオーダーnです。並べ替えは最高の順序n(log n)です。最悪でもn ²。

Answer 3

おそらく最も速いのは、アレイが見つかるまでスキャンすることです。

これを 1 回だけ実行し、他の目的で配列をソートする必要がない場合は、ソートを実行するよりも負の数をスキャンする方が高速です。ただし、他の目的で並べ替えが必要な場合 (または使用できる場合)、または負の数を数回見つける必要がある場合は、並べ替えによって時間を節約できます。同様に、一部のプログラムでは、非常に重要な場合に迅速な応答を得るために準備に余分な時間を費やすことが正当化されます (ただし、それがここに当てはまるかどうかはわかりません)。