Помните, что когда время выполнения алгоритма указано с помощью O-обозначения, оно
«Асимптотический». Слишком упрощенное время выполнения O(log n) означает, что ваша программа выполняет c*log n шагов, где c - некоторая константа, которую вы на самом деле не знаете. Это может быть довольно большим. Поэтому использование действительных чисел в формулах для времени выполнения не даст вам точных результатов.
Вот два подхода, чтобы найти ответ на ваш вопрос:
Вы можете запустить несколько тестов для разных входов, чтобы сравнить два метода. Выберите тот, который лучше всего подходит для вашего приложения.
Вы можете сделать более глубокий теоретический анализ:
Допустим, в массиве n элементов, которые вы хотите найти,
и вы хотите найти k элементов. Итак, в вашем примере, n = 1000000
и k = 100.
Если вы сортируете и используете бинарный поиск для каждого элемента,
вы используете O(n log n) время для сортировки и O(k log n) время для
поиск, в общей сложности O(n log n + k log n). Если вы делаете линейный
Для поиска каждого из k элементов вы используете O(kn) время.
Теперь, если k = O(log n), то O(kn) становится O(n log n), и с использованием двух методов
должно быть одинаково быстро (асимптотически). Однако, если k = Omega(log n) (т.е. k
ограничен снизу log n), затем n log n = O(kn), и сортировка перед поиском выполняется быстрее (асимптотически).
Это означает, что вы можете использовать некоторый тест типа k < c log n для некоторой константы c и использовать метод линейного поиска, если тест пройден успешно, и метод sort + search в противном случае. Точное значение c должно быть определено с помощью тестов и тестов, опять же из-за асимптотики времени выполнения.
БОНУС
Существует еще один забавный алгоритм, который вы можете использовать, если заранее знаете все значения k. Пусть A будет n цифрами, в которых вы хотите искать, и B будет k цифрами, которые вы хотите найти.
- Сортировка
B (O(k log k) время)
- Выполните итерацию по
A, и для каждого элемента e выполните бинарный поиск в B для e (всего O(n log k))
Таким образом, вы определите, какие числа в B также находятся в A, и потребуется O(n log k + k log k), что асимптотически быстрее (или так же быстро), как и другие методы, если k = O(n) (для экземпляр, если k < n).