考虑以下元组列表：[(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)。
谢谢！
考虑这个问题的 2 元组版本。每个元组 (x,y) 对应于平面上的一个轴对齐矩形，右上角为 (x,y)，右下角为 (-oo,+oo)。该集合对应于这些矩形的并集。给定一个查询点（针），我们只需要确定它是否在联合中。知道边界就足够了。它是一条轴对齐的折线，y 相对于 x 单调不增加：x 方向上的“向下阶梯”。使用任何合理的数据结构（例如，折线上的 x 排序的点列表），很容易在 O(log n) 时间内对 n 个矩形做出决定。不难看出如何在 O(n log n) 时间内通过一次插入一个矩形来构造折线，每个矩形都有 O(log n) 的工作量。
这是一个可视化。四个点是输入元组。蓝线左侧和下方的区域对应于“True”返回值：
元组 A、B、C 影响边界。元组 D 没有。
所以问题是这个 2 元组版本是否可以很好地推广到 3。半无限轴对齐矩形的并集改为矩形棱柱的并集。边界多段线变为 3d 曲面。
存在一些常见的方法来表示这样的问题。一种是八叉树。计算八叉树的并集是一种众所周知的标准算法并且相当有效。查询一个成员需要 O(log k) 时间，其中 k 是其中包含的最大整数坐标范围。这可能是最简单的选择。但是如果整数域很大，八叉树可能会相对较慢并且占用大量空间。
另一个没有这些弱点的候选者是二进制空间分区，它可以处理任意维度。BSP 使用维度为 n-1 的（超）平面来递归分割 nd 空间。树描述了平面的逻辑关系。在这个应用程序中，每个元组需要 3 个平面。由平面诱导的“真”半空间的交点将是对应于元组的真半无限棱镜。查询针正在遍历树以确定您是否在任何棱镜内。BSP 的平均情况表现非常好，但树的最坏情况大小很糟糕：在大小为 O(2^n) 的树上的搜索时间为 O(n)。在实际应用中，技巧用于在创建时找到大小适中的 BSP，从随机插入顺序开始。
Kd 树是另一种可以适应这个问题的基于树的空间划分方案。不过，这需要一些工作，因为 kd 树的大多数表示都与搜索点有关，而不是表示区域。他们将具有与 BSP 相同的最坏情况行为。
另一个坏消息是这些算法不太适合大于 3 的元组。树很快就会变得太大。搜索高维空间是困难的，也是一个积极研究的话题。但是，由于您没有提及元组长度，我将在此停止。
空间索引系统解决了这类问题。有许多数据结构可以让您的查询有效地执行。
令 S 是每个 m 元组的原始集合的拓扑排序副本。然后我们可以对 S 中的任何测试元组使用二进制搜索，每次搜索的成本为 O(m ln n)（由于最多 lg n 个搜索层，每个层最多进行 m 个比较）。
注意，假设 S 中存在元组 P、Q，使得 P ≤ Q（即 Q 中没有一个元素小于 P 的对应元素）。然后可以从 S 中删除元组 Q。在实践中，这通常可能会将 S 的大小减少到 m 的小倍数，这将给出 O(m ln m) 的性能；但在最坏的情况下，根本不会提供任何减少。
尝试回答
（使用y和z表示集合/干草堆栈的成员，使用x表示查询元组/针，当 xₐ ≤ yₐ 表示所有 ₐ 时使用x ll y （ x 以y为主））
allcorrespondingelements greater than or equal to a given tuple (needle)