Методы поиска datastructures

Question

У меня проблема с вопросом в бумаге, которая была передана мне, и я надеюсь, что кто-то сможет мне помочь. Вопрос:

a) Маленькая книга птиц с 100 заглавными буквами и большой книгой птиц с 1000 заглавными буквами хранится в форме, доступной для поиска в компьютере. Это занимает примерно 50% в течение длительного времени, чтобы искать большую книгу птиц как книгу с маленькими птицами. Какой метод поиска используется?

b) Теперь метод хранения и поиска заменяется. Теперь для поиска обеих книг требуется столько же времени. Какой новый метод поиска?

Итак, первый вопрос о сложности O (log (n)), и я не знаю ни одного метода поиска с такой сложностью времени. Второй должен быть порядка O (1), так как они занимают одинаковое количество времени?

Answer 1

Binary search имеет асимптотическую сложность O(log n). Если предполагается, что длина заглавных слов является постоянной, алгоритм hash-based может извлекать элементы в постоянное время, см., Например, hash tables.