Является самым быстрым алгоритмом для поиска несортированного массива для линейного поиска элемента? Я имею в виду, я предполагаю, что комбинация слияния сортировки + двоичный поиск будет медленнее. Есть ли другие варианты? (в терминах алгоритмов, не включающих многопоточность)?Самый быстрый способ найти, существует ли элемент в несортированном массиве?
Да, если массив несортирован, и это все, что вы знаете о его структуре, то самым быстрым способом поиска элемента является рассмотрение каждого, которое принимает линейное время. O (n).
Если вы собираетесь много искать массив, вы можете захотеть рассмотреть начальную сортировку, а затем вставить элементы в их правильный отсортированный индекс (используя двоичный поиск). Это означает, что у вас есть ваш первоначальный вид: O (n log n), но каждая вставка и поиск принимают O (log n). Все дело в компромиссах и лучше, чем O (1) Вставка и O (n) поиск.
Вы сказали, что не многопоточность, но это простой способ повысить производительность, несколько потоков смотрят на разные куски в списке.