Сложность линейного поиска нескольких элементов в списке ⇐ JAVA

[Anonymous]

Я сравниваю поиск методом перебора и свой собственный подход к поиску.
Проблема возникла при оценке сложности поиска методом перебора. В рамках поиска мне нужно проверить, находятся ли указанные элементы в несортированном списке элементов.
Приведу упрощенный пример для списка целых чисел. У меня есть целочисленный список с элементами [1..100_000]. Я просматриваю все элементы линейно и рассчитываю, сколько сравнений мне нужно сделать, чтобы найти все искомые элементы. В моем случае сравнение проверяет search.contains(values.get(i)) из примера кода ниже.
Мои результаты следующие:

• Для 1 искомого элемента: около 50_000 сравнений, что равно O(N/2). Мне это ясно. Лучший случай – 1, худший – 100_000, а средний – 50_000.
• Для 2 искомых элементов: около 65_000 сравнений. Но почему? Что такое математическая формула или вычислительная сложность?
• Для 3 искомых элементов: около 75_000 сравнений. Но почему? Что такое математическая формула или сложность вычислений?

Снимок экрана моего теста с 1_000 прогонами:


Мой следующий код на Java.
Я проверяю те же элементы, но копия списка перемешивается перед каждым поиском.
public static void main(String[] args) {
List values = IntStream.range(1, 100_000).boxed().toList();

List results1 = new ArrayList();
List results2 = new ArrayList();
List results3 = new ArrayList();

Set search1 = Set.of(1);
Set search2 = Set.of(1, 2);
Set search3 = Set.of(1, 2, 3);

for (int i = 0; i < 1000; i++) {
results1.add(search(values, search1));
results2.add(search(values, search2));
results3.add(search(values, search3));
}
System.out.println("Search 1: " + results1.stream().mapToInt(i->i).average().getAsDouble());
System.out.println("Search 2: " + results2.stream().mapToInt(i->i).average().getAsDouble());
System.out.println("Search 3: " + results3.stream().mapToInt(i->i).average().getAsDouble());
}

private static int search(List list, Set search) {
List values = new ArrayList(list);
Collections.shuffle(values);

int i = 0;
int found = 0;
for (; i < values.size(); i++) {
if (search.contains(values.get(i))) {
++found;
}
if (found == search.size()) {
break;
}
}
return i+1;
}


Подробнее здесь: https://stackoverflow.com/questions/785 ... n-the-list