튜플 집합, 주어진 숫자를 포함하는 튜플을 찾는 방법

Question

주어진 숫자가 집합에 있는지 확인하는 데 O (1) 시간이 걸린다는 것을 알고 있습니다. 내 질문에 만약 내가 일련의 튜플이 있다면, 어떤 숫자가 어떤 튜플에 속하면 O (1) 시간을 체크 한 다음 튜플을 리턴 할 수 있을까?

Answer 1

시간 복잡도는 구현에 따라 달라집니다.

튜플 배열이 있다고 가정 해 보겠습니다. 귀하의 질문에 을 알고있는 경우 튜플을 검색하면 복잡성은 O(1)이며 알려진 튜플을 직접 인덱싱하고 쿼리를 완료합니다.

그러나 배열의 모든 튜플을 반복하여 원하는 대상을 찾으려면 검색 구현에 따라 복잡도가 O(n) 또는 O(n lg n)이 될 수 있습니다.