java - Java Search algorithm

Question

Can any one tell the java example/algorithm to search element in an array with following implementation:
- O(n^2) algorithm and
- O(n) algorithm

Note: This is not a homework.

Answer 1

• 配列内の単一のアイテムを検索することはO(N)
• 配列内の増加する数値の最長の実行を検索するのは、O(N^2)2 つのネストされたループを含む単純なアルゴリズムを使用する場合です^*

注: これはJava 固有のものではありません。

---

^*この検索を行うためのより高速なアルゴリズムが存在します。

Answer 2

O(n²)検索アルゴリズムを実行しても意味がありません。

アルゴリズムを実行するO(n)には、リスト内の要素を検索するだけです。

for(int i=0;i<array.length;i++)
  if(array[i]==search)
    return array[i];

Answer 3

単純O(n)な線形検索になります。探しているものが見つかるまで、リストを最初から最後までたどります。

アルゴリズムが必要なのは奇妙ですO(n²)...しかし、できることは、(O(n)検索での) for ループの各反復で、配列の長さ ( ) で定義された期間だけスリープすることThread.sleep(array.length)です。「スリープ」期間はO(n)、配列の長さに線形に依存するため、線形検索全体も になるO(n)ため、全体のプロセスは になりますO(n²)。

---

O(n)

for (int i = 0 ; i < array.length ; i++) {
    if (array[i] == SOME_ELEMENT) {
        // ...
        break;
    }
 }    

O(n²)

for (int i = 0 ; i < array.length ; i++) {
    Thread.sleep(array.length);
    if (array[i] == SOME_ELEMENT) {
        // ...
        break;
    }
 }