Найти неправильные объекты из списка, чтобы сохранить сетевые запросы

Question

У меня есть 100 объектов, некоторые из них правильные, а другие могут быть неправильными.
Я хотел бы найти исправления только объектов из 100.

У меня есть функция bool isCorrect(List<object> objs) (O(1)), которая получает x объектов и возвращает false, если хотя бы один объект неверен - я не могу изменить эту функцию.

Каждый isCorrect звонок делает запрос сети. Таким образом, вы хотели бы сохранить запросы.

Что Iv пробовал?
1. Запустите каждый объект isCorrect - O(n)
2. Запустите бинарный поиск - если 100 возвращает неправильное разделение на 50 50 и т. Д. c ... - O(log2(N)).

Худший случай - O(log2(N)) + O(N)
Могу ли я найти какой-нибудь другой алгоритм лучше этого?

Answer 1

O (n) доказуемо оптимально в худшем случае.

Рассмотрим семейство входов, где все объекты, кроме одного, неверны. Выходными данными должен быть список, содержащий только этот объект, но единственный способ найти его - это проверить объекты по одному; любой тест для более чем одного объекта всегда будет возвращать true, потому что хотя бы один из них неверен.

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

Answer 2

Эта проблема чувствительна к выводу . Предположим, что вы выводите список правильных последовательностей объектов, тогда минимальная сложность, которую вы можете достичь, - Омега (длина этого списка).