Сколько времени O при определении, находится ли значение в отсортированном массиве?

Question

У меня есть отсортированный массив из 5000 целых чисел. Как быстро я могу определить, является ли случайное целое число членом массива? Ответ в общем, C и Ruby были бы хорошими.

Значения массива имеют вид

c * c + 1

, где c может быть любым целым числом от 1 до 5000.

Например:

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

Answer 1

log (n) для двоичного поиска на c

Answer 2

Я бы сказал, что это O (const)! :)

Учитывая случайное число r, тривиально проверить, может ли оно быть представлено в форме (n * n + 1). Просто проверьте, является ли sqrt (r-1) целым числом или нет!

(Ну, это может быть немного сложнее, поскольку ваш язык программирования может внести некоторую сложность в работу с целыми числами против чисел с плавающей запятой, но все же: вам вообще не нужно искать в массиве: просто проверьте, является ли номер в этой конкретной форме.)

Answer 3

Бинарный поиск, как уже упоминалось, имеет значение 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) ваших номеров. С помощью всего лишь 5000 слов памяти вы можете достичь O (1) поиска таким образом.

Пояснение:

Поскольку все ваши числа имеют форму N ^ 2 + 1 для целого числа N от 1 до N, вы можете создать таблицу из 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).

Answer 4

Технически сложность поиска элемента в массиве фиксированного размера постоянна, поскольку log ₂ 5000 не изменится.

Answer 5

Двоичный поиск - O (log n)

WikiPedia

Answer 6

Просто вкратце: это lg n тестов, то есть log ₂ n. Это делает его O ( log n) . Зачем? потому что каждое испытание бинарного поиска делит массив пополам; таким образом, требуется LG N испытаний.

Answer 7

O (log n), если массив имеет n элементов

Answer 8

В Perl:

Я бы загрузил значения в статический хеш, и тогда это было бы O (1).

Создание хеша Lookup

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

Синтаксис поиска

($ lookup_hash {$ lookup_value}) && print "Найдено в O (1) - здесь нет цикла \ n";

Answer 9

Используя бинарный поиск, это время поиска по журналу (N).

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