1

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

配列値の形式は次のとおりです。

c * c + 1

ここでc、1 から 5000 までの任意の整数を指定できます。

例えば：

[2, 5, 10, 17, 26, 37, 50 ...]
4

9 に答える 9

15

c の二分探索の場合は log(n)

于 2009-01-22T20:06:11.023 に答える
10

私はそれがO（const）だと思います！:)

乱数 r が与えられた場合、それが (n*n+1) の形式で表現できる数値かどうかを確認するのは簡単です。sqrt(r-1) が整数かどうかをチェックするだけです!

(ええと、それよりも少し複雑かもしれません。なぜなら、あなたのプログラミング言語は整数と浮動小数点数の扱いにいくらかの複雑さをもたらす可能性があるからです。それでも: 配列を検索する必要はまったくありません: 数値が含まれているかどうかをチェックするだけです)この特定のフォーム。)

于 2009-01-22T20:20:53.537 に答える
6

他の人が述べたように、バイナリ検索は 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) です。

于 2009-01-22T20:11:33.743 に答える
5

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

于 2009-01-22T20:23:01.287 に答える
2

二分探索は O(log n)

ウィキペディア

于 2009-01-22T20:07:47.667 に答える
1

O(log n) (配列が n 要素の場合)

于 2009-01-22T20:07:00.273 に答える
1

それを拡張すると、これはlg nテスト、つまりlog 2 n です。それはO( log n)になります。なんで？二分探索の試行ごとに配列が半分に分割されるためです。したがって、lg n 回の試行が必要です。

于 2009-01-22T20:09:22.577 に答える
0

パールでは:

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

ルックアップ ハッシュを構築する

lookup_hash{$_} = 1 foreach (@original_array);

ルックアップ構文

($lookup_hash{$lookup_value}) && print "O(1) で見つかりました - ここにはループはありません\n";

于 2009-01-22T20:31:46.963 に答える
0

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

bool ContainsBinarySearch(int[] array, int value) {
  return Array.BinarySearch(arrray, value) >= 0;
}
于 2009-01-22T20:07:11.520 に答える