我有100个对象，其中一些是正确的，另一些可能是不正确的
我只想从100中查找个对象。
我有一个函数bool isCorrect(List<object> objs)(O(1)(，它获取x个对象，如果至少有一个对象不正确，则返回false——我无法更改该函数。
每个isCorrect呼叫都会发出一个网络请求。因此，您希望保存请求。
Iv尝试了什么
1.运行每个对象isCorrect-O(n)
2。运行二进制搜索-如果100是，则返回不正确的拆分为50 50等…-O(log2(N))。
最坏的情况是O(log2(N))+O(N)
我能找到比这更好的其他算法吗？
这个问题对输出敏感。假设你的输出是正确的对象序列列表，那么你能达到的最小复杂度是Omega(这个列表的长度(。
O(n(在最坏情况下是可证明的最优。
考虑输入族，其中除一个对象外的所有对象都不正确。输出必须是一个只包含该对象的列表，但找到它的唯一方法是一次测试一个对象；对多个对象的任何测试都将始终返回CCD_ 9，因为其中至少有一个是不正确的。
这意味着您需要在最坏的情况下对单例列表进行n次测试，这需要O(n(时间。你确实需要做所有n个测试，因为如果你跳过其中任何一个，你可能会错过一个正确的对象。