java - Java の Big-O 表記

Question

ねえ、誰かが私のために大きなo表記を説明できますか?

Answer 1

配列があるので、それは連続したメモリを意味します。これは、リンクリストのように繰り返す必要がないため、任意のインデックスでのルックアップが1つのアクションで行われることを意味します。つまり、O（1）です。

ArrayList Aの各要素はBの各要素と比較する必要があるため、順序付けや並べ替えを行わずに2つのArrayListオブジェクトAとBを比較すると、O（n ^ 2）になります。したがって、Aにはn個の要素、Bにはn個の要素があります。 Aのすべての要素にBとのn回の比較が必要になります。Aにはn個の要素があるため、n回のn回の比較、つまりO（n ^ 2）です。

並べ替えアルゴリズムを使用した場合でも、使用する並べ替えアルゴリズムに応じて、O（n log n）時間やO（n）などの並べ替えアルゴリズムと同じ速度になります。

ソートされていない配列で特定のターゲット値を検索するのは、確かにO（n）です。これが当てはまるのは、配列内のすべての要素を検索して、それが存在するかどうかを確認する必要があるためです。リストにはn個の要素があるため、n個の比較があることを意味します。

Answer 2

1-配列要素にはランダムにアクセスできるため（リンクリストのようにあるセルから別のセルに移動する必要はありません）、基本的にO（1）であるarray [28]と言えます

2- 2 つの配列リストを比較すると、big-O が低くなるような方法で実行できます。ただし、並べ替えを使用します。

マージソートまたはクイックソート O(nlg(n)) を使用して各配列リストをソートし、O(n) でソートされた 2 つのリストを比較できます。結果は O(nlgn) です。

しかし、別のアルゴリズム (並べ替えなし) は、1 つの配列 (n) 内の各要素を反復処理します。次に、要素が別の配列 (n) であるかどうかを確認します (重複を適切に処理するためにマークします)。この後者のアルゴリズムは O(n^2) です。

3- はい、そうです。目的の要素が見つかるまで、リスト全体を 1 つずつ確認する必要があります。