java - メソッドがNかN^2かを知る方法

Question

皆さんが N メソッドや N^2 メソッドについて話しているのをよく見かけますが、間違っていたら訂正しますが、メソッドの速さを示しています。私の質問は次のとおりです。どのメソッドが N で、どれが N^2 であるかをどのように知っていますか? また、N と N^2 だけでなく、メソッドの他の速度表示はありますか?

Answer 1

これは、アルゴリズムの複雑さについて語っています（これは、アルゴリズムがどれだけ高速になるかの指標です）

つまり、サイズ「N」のメソッドへの入力に必要な「操作」(操作は非常に曖昧で抽象的な用語です) の数を示します。

たとえば、入力がリスト型のオブジェクトで、リスト内のすべての項目を反復処理する必要がある場合、複雑さは "N" です。(しばしば O(N) と表されます)。

入力がリスト型のオブジェクトで、最初 (または最後) だけを見る必要があり、そのような項目の見方が O(1) であることをリストが保証している場合。メソッドは O(1) になります-入力サイズとは無関係です。

入力がリストで、すべてのアイテムを他のすべてのアイテムと比較する必要がある場合、複雑さは O(N²) または O(N*log(n)) になります。

Answer 2

間違っている場合は訂正してください。メソッドの速度を示してください。

それは、アルゴリズムが理想的なマシンでどのようにスケーリングするかを示しています。これは、O(1) が O(N) よりも遅くなる可能性があり、ユース ケースの O(N^2) よりも遅くなる可能性があることを意味する関連する要因を意図的に無視します。たとえば、Arrays.sort() は、小さなコレクション (Java 7 では長さ < 47) に対してクイックソート O(N ln N) よりも挿入ソート O(N^2) を使用します。

一般に、完全にテストする機会が得られない極端なケースで壊れる可能性が低いため、低次アルゴリズムを使用する方が安全な選択です。

Answer 3

プログラムのbig-Oの複雑さを推測する方法は、コードをドライランする（頭の中で実行する）経験に基づいています。明らかなケースもありますが、最も興味深いケースはそうではありません。たとえば、O（n）ループでO（n）として知られているライブラリメソッドを呼び出すと、O（n ²）全体が複雑になります。O（n）ループでaに書き込むと、TreeMap合計でO（nlogn）というようになります。