В чем заключаются логарифмический и константный алгоритмы поиска по базе данных через язык C++?
Подскажите, пожалуйста, как можно оптимизировать алгоритм поиска по базе данных, используя только сторонние файлы, без массивов и других структур языка(не линейно). Знаю, что есть такие алгоритмы, как логарифмический и константный, но не знаю, в чём они заключаются и как реализуются.
Ответы (1 шт):
вам тут в 2х словах не объяснить, но можно чуть-чуть намекнуть :)
смотрите - скажем вы храните телефонные номера
если вы отсортируете номера по возрастанию, то определить, есть ли телефон в базе можно за O(log(N)) времени используя бинарный поиск (для 4 миллиардов чисел вам потребуется всего максимум 32 операции обращения к таблице, а для миллиона чисел - 20 операций)
если же вам нужен не конкретно телефонный номер, а узнать страну (первые 1-2 цифры номера), то все номера можно разбить на 100 групп и база будет содержать только 100 ячеек со значениями 0/1 - есть номер или нет номера
тогда для того, чтобы узнать есть ли у страны телефонные номера вам достаточно сразу обратиться к ячейке №N (первые 2 цифры) - это потребуется константное время O(1), т.е. 1 обращение к таблице
Когда в таблице хранятся не числа, а сложные данные, то используется хэширование - по сложным данные вычисляется некоторое значение (число), которое опять же можно отсортировать и искать данные бинарным поиском за O(log(N)) времени
Например, вам надо найти в таблице некоторый текст.
По каждому тексту вычисляется хэш-сумму (например CRC32 или MD5) и в таблице хранятся индексы - связка Hash:Index - хэш и указатель на данные соответствующие этому хэшу.
Когда вы хотите найти некоторый текст в таблице, то по нему вычисляется хэш (скажем некоторое значение 129827172) и ищется именно это значения за O(log(N))время, когда запись находится, то смотрится куда она ссылается и дальше уже получается доступ к данным