Каково время O при определении того, находится ли значение в отсортированном массиве?
-
19-08-2019 - |
Вопрос
У меня есть отсортированный массив из 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)
из ваших номеров.Имея всего 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).
Другие советы
log (n) для бинарного поиска на c
Я бы сказал, что это O (const)! :) Р>
Учитывая случайное число r, тривиально проверить, может ли это число быть представлено в форме (n * n + 1). Просто проверьте, является ли sqrt (r-1) целым числом или нет! Р>
(Ну, это может быть немного сложнее, чем то, поскольку ваш язык программирования может внести некоторую сложность в работу с целыми числами по сравнению с числами с плавающей запятой, но все же: вам вообще не нужно искать в массиве: просто проверьте, является ли номер в этой конкретной форме.)
Технически сложность поиска элемента в массиве фиксированного размера постоянна, поскольку log 2 5000 не собирается меняться.
Двоичный поиск - O (log n)
O (log n), если массив имеет n элементов
Просто скажем подробнее: это lg n , то есть log 2 n. Это делает его O ( log n) . Зачем? потому что каждое испытание бинарного поиска делит массив пополам; таким образом, требуется LG N испытаний.
При использовании бинарного поиска это время поиска по журналу (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 " нашел его в O (1) - здесь нет цикла \ n " ;;