Как найти конкретную строку в массиве или связном списке

Question

Я хочу найти строку с определенным массивом коротких строк или связанным списком.Я создаю небольшую программу для поиска конференций или семинаров, например http://dblp.uni -trier.de / , используя c ++.Что мне интересно, так это как быстро искать строку в массиве или связанном списке.Когда я использую функцию string.find (), я думаю, что производительность этой функции имеет O (n) временную сложность, если длина массива равна n.Могу ли я улучшить производительность ниже, чем O (n)?Помогите мне, пожалуйста

Answer 1

Если вы действительно хотите усложнить свой код, при каждой вставке хранить список указателей на узлы в некотором сбалансированном дереве. Куда узлы будут вставлены на основе строки из этого сравнения узлов.Затем вы можете получить строку за O (logn).

Если вы хотите получить быстрый поиск, используйте хэш-карту, это даст вам O (1) Time.

Answer 2

Для массива, если он не отсортирован, лучшее, что вы можете сделать, это O (n) средний / наихудший случай, потому что вы должны смотреть линейно, пока не найдете нужную строку.Если он отсортирован (что потребует O (nlog (n)), чтобы выполнить сортировку), вы можете сделать это O (log (n)), используя двоичный поиск.Для связанных списков лучшее, что вы можете сделать, независимо от сортировки, это O (n).