순서가 지정되지 않은 개체 목록을 효율적으로 비교하는 방법은 무엇입니까?

순서가 지정되지 않은 목록의 효율적인 비교

백이라고도 하는 순서가 지정되지 않은 목록을 비교하는 것은 어려운 작업일 수 있으며, 특히 정수와 같은 단순한 데이터 유형 대신 개체를 사용하여 작업할 때 더욱 그렇습니다. . 이 문제를 해결하기 위한 세 가지 효율적인 접근 방식은 다음과 같습니다.

1. 카운터 메서드(O(n))

해시 가능한(즉, 고유한 해시 값으로 변환할 수 있는) 개체의 경우 Python 컬렉션 모듈의 Counter() 메서드를 사용할 수 있습니다. 키가 목록의 요소이고 값이 각각의 개수인 사전과 같은 객체를 생성합니다. 이 접근 방식을 사용하여 두 목록을 비교하면 O(n)의 선형 시간 복잡도가 있습니다. 여기서 n은 목록의 길이입니다.

import collections

def compare(s, t):
    return collections.Counter(s) == collections.Counter(t)

2. 정렬 방법(O(n log n))

목록의 개체가 비교 가능한 경우(즉, 순서가 정의된 경우) 목록을 정렬하면 효율적인 비교 메커니즘을 제공할 수 있습니다. Python의 sorted() 메서드는 목록의 요소를 정렬하여 두 목록에 어떤 순서로든 동일한 요소가 포함되어 있는지 쉽게 확인할 수 있습니다. 이 접근 방식은 O(n log n)의 시간 복잡도를 가지며, 여기서 n은 목록의 길이입니다.

def compare(s, t):
    return sorted(s) == sorted(t)

3. 동등 비교(O(n * n))

객체가 해시 가능하지도 않고 정렬 가능하지도 않은 경우 간단한 접근 방식은 두 목록의 요소 간에 동등 비교를 수행하는 것입니다. 첫 번째 목록의 각 요소에 대해 두 번째 목록에서 제거합니다. 첫 번째 목록의 요소가 두 번째 목록에서 발견되지 않으면 비교가 실패합니다. 이 접근 방식은 최악의 경우 O(n * n)의 시간 복잡도를 갖습니다. 여기서 n은 목록의 길이입니다.

def compare(s, t):
    t = list(t)  # make a mutable copy
    try:
        for elem in s:
            t.remove(elem)
    except ValueError:
        return False
    return not t

이러한 효율적인 비교 기술을 활용하면 순서가 지정되지 않은 개체 목록을 효과적으로 비교할 수 있습니다. , 해시 가능 여부, 주문 가능 여부, 또는 둘 다 불가능 여부.

위 내용은 순서가 지정되지 않은 개체 목록을 효율적으로 비교하는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!