0
튜플의 다음 목록을 고려하십시오. [(5,4,5), (6,9,6), (3,8,3), (7,9,8]]주어진 튜플보다 큰 모든 요소를 가진 튜플을 효율적으로 검색하십시오.
나는 그 튜플의 모든 원소가 주어진 튜플 (바늘)보다 크거나 같은리스트에 적어도 하나의 튜플이 존재하는지 확인하기 위해 알고리즘을 고안하려고한다.
예를 들어 주어진 튜플 (6,5,7)의 경우 알고리즘은 주어진 튜플의 모든 요소가 목록의 첫 번째 튜플 인 (5,4,5)보다 작기 때문에 True를 반환해야합니다. 그러나 주어진 튜플 (9,1,9)의 경우 알고리즘은 각 요소가 주어진 튜플보다 큰 목록에 튜플이 없으므로 False를 반환해야합니다. 특히 이것은 주어진 튜플의 두 번째 요소 1에 기인합니다.이 요소는 목록의 모든 튜플의 두 번째 요소보다 작습니다.
순진한 알고리즘은 목록의 튜플을 하나씩 반복하고 내부 루프의 튜플 요소를 반복합니다. n 개의 튜플이 있다고 가정하면, 각 튜플에는 m 개의 요소가 있습니다. 이것은 O (nm)의 복잡성을 줄 것입니다.
복잡도가 낮은 작업을 생성하는 알고리즘을 사용할 수 있을지 생각 중입니다. 데이터를 저장하기위한 전처리 또는 멋진 데이터 구조가 허용됩니다!
필자의 원래 생각은 이진 검색의 변형을 사용하는 것이었지만 첫 번째 튜플을 기반으로 일부 튜플을 제거한 후에는 순진한 솔루션으로 되돌릴 수없는 데이터 구조를 찾지 못했습니다. 이 알고리즘은 결국에는 O (nm)가 될 수 있음을 의미합니다.
감사합니다.
포인터 주셔서 감사합니다! 나는 그것을 들여다 볼 것이다! – Paul