値がソートされた配列内にあるかどうかを判断するO時間は何ですか？

StackOverflow https://stackoverflow.com/questions/470605

質問

5000個の整数のソート済み配列があります。ランダムな整数が配列のメンバーであるかどうかはどれくらい速くわかりますか？一般的な答えは、CとRubyがいいでしょう。

配列の値は次の形式です

c * c + 1

ここでcは1〜5000の任意の整数です。

例：

[2, 5, 10, 17, 26, 37, 50 ...]
役に立ちましたか？

解決

他の人が述べたように、バイナリ検索はO（log2N）であり、再帰的にコーディングできます：

   BinarySearch(A[0..N-1], value, low, high) {
       if (high < low)
           return -1 // not found
       mid = (low + high) / 2
       if (A[mid] > value)
           return BinarySearch(A, value, low, mid-1)
       else if (A[mid] < value)
           return BinarySearch(A, value, mid+1, high)
       else
           return mid // found
   }

または反復的に：

   BinarySearch(A[0..N-1], value) {
       low = 0
       high = N - 1
       while (low <= high) {
           mid = (low + high) / 2
           if (A[mid] > value)
               high = mid - 1
           else if (A[mid] < value)
               low = mid + 1
           else
               return mid // found
       }
       return -1 // not found
   }

ただし、可能な限り高速な方法を探している場合は、数字のsqrt(N-1)に基づいてルックアップテーブルを設定できます。 5,000ワードのメモリで、この方法でO（1）ルックアップを実現できます。

説明：

すべての数値は1からNまでの整数Nに対してN ^ 2 + 1の形式であるため、N個の要素のテーブルを作成できます。位置iの要素は、i ^ 2 + 1が配列内にあるかどうかを指定します。テーブルは、長さNの単純な配列で実装できます。構築にはO（N）とNワードのスペースが必要です。ただし、テーブルが作成されると、すべてのルックアップはO（1）になります。

例：

ここにPythonのサンプルコードがあります。これはいつものように擬似コードのように読みます：-）

import math

N = 5000
ar = [17, 26, 37, 50, 10001, 40001]

lookup_table = [0] * N

for val in ar:
    idx = int(math.sqrt(val - 1))
    lookup_table[idx] = 1

def val_exists(val):
    return lookup_table[int(math.sqrt(val - 1))] == 1

print val_exists(37)
print val_exists(65)
print val_exists(40001)
print val_exists(90001)

テーブルの構築は最大でO（N）を占有し、ルックアップはO（1）です。

他のヒント

cのバイナリ検索の場合はlog（n）

O（const）だと思います！ ：）

乱数rが与えられた場合、それが（n * n + 1）の形式で表現できる数であるかどうかを確認するのは簡単です。 sqrt（r-1）が整数かどうかを確認してください！

（まあ、プログラミング言語は整数と浮動小数点数の処理に多少の複雑さをもたらす可能性があるため、それよりも少し複雑かもしれませんが、それでも：配列を検索する必要はありません：番号はこの特定の形式です。）

技術的には、log 2 5000は変わらないため、固定サイズの配列で要素を見つける複雑さは一定です。

バイナリ検索はO（log n）です

WikiPedia

O（log n）配列にn個の要素がある場合

それを拡張するだけです： lg n テスト、つまり log 2 nです。これにより、 O（ log n）になります。どうして？バイナリ検索の各試行では配列が半分に分割されるためです。したがって、 lg n回の試行が必要です。

バイナリ検索を使用すると、Log（N）検索時間になります。 

bool ContainsBinarySearch(int[] array, int value) {
  return Array.BinarySearch(arrray, value) >= 0;
}

Perlの場合：

値を静的ハッシュにロードすると、O（1）になります。

ルックアップハッシュの構築

lookup_hash {$ _} = 1 foreach（@original_array）;

ルックアップ構文

（$ lookup_hash {$ lookup_value}）<！> amp; <！> amp; print <！> quot; O（1）で見つかりました-ループはありません\ n <！> quot ;;

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top