algorithm - 有效地搜索所有元素都大于给定元组的元组

Question

考虑以下元组列表:
[(5,4,5), (6,9,6), (3,8,3), (7,9,8)]

我正在尝试设计一种算法来检查列表中是否至少存在一个元组，其中该元组的所有元素都大于或等于给定的元组(针)。

例如，对于给定的元组 (6,5,7)，算法应该返回 True，因为给定元组中的每个元素都小于列表中的最后一个元组，即 (7,9,8)。但是，对于给定的元组 (9,1,9)，算法应该返回 False，因为列表中没有每个元素都大于给定元组的元组。特别是，这是由于给定元组的第二个元素 1 小于列表中所有元组的第二个元素。

一个简单的算法会一个一个地遍历列表中的元组，并在内循环中遍历元组的元素。假设有 n 个元组，其中每个元组有 m 个元素，这将给出 O(nm) 的复杂度。

我在想是否有可能有一种算法来生成复杂度较低的任务。允许预处理或任何花哨的数据结构来存储数据!

我最初的想法是利用二进制搜索的一些变体，但我似乎无法找到一种数据结构，一旦我们基于第一个元素消除了一些元组，我就不会退回到朴素的解决方案，这意味着该算法最终也可能是 O(nm)。

谢谢!

Answer 1

这种问题由 spatial indexing 系统解决。有许多数据结构可以让您的查询高效执行。