次のタプルのリストを考えてみましょう: [(5,4,5), (6,9,6), (3,8,3), (7,9,8)]
リスト内に、そのタプルのすべての要素が特定のタプル (針) 以上であるタプルが少なくとも 1 つ存在するかどうかをチェックするアルゴリズムを考案しようとしています。
たとえば、特定のタプル (6,5,7) の場合、特定のタプルのすべての要素がリストの最後のタプル (7,9,8) より小さいため、アルゴリズムは True を返す必要があります。ただし、特定のタプル (9,1,9) の場合、リストには各要素が特定のタプルより大きいタプルがないため、アルゴリズムは False を返す必要があります。特に、これは、リスト内のすべてのタプルの 2 番目の要素よりも小さい、指定されたタプルの 2 番目の要素 1 によるものです。
単純なアルゴリズムは、リスト内のタプルを 1 つずつループし、内側のループでタプルの要素をループします。n 個のタプルがあり、各タプルに m 個の要素があると仮定すると、O(nm) の複雑さが得られます。
複雑さの低いタスクを生成するアルゴリズムを持つことが可能かどうかを考えています。データを保存するための前処理または任意の派手なデータ構造が許可されています!
私の最初の考えは、バイナリ検索のいくつかの変形を利用することでしたが、最初の要素に基づいていくつかのタプルを削除した後、単純なソリューションに戻らないようにするデータ構造を見つけることができないようです。このアルゴリズムは、最後に O(nm) になる可能性もあります。
ありがとう！