스텝 키에 의한 스러스트 정렬 및 추력의 복잡성

Question

추력에서 키 기능별 정렬 및 고유 기능을 사용하고 있습니다. 나는 단지 추력의 정렬 함수의 단계 복잡도와 주요 함수에 의한 고유 한 작업 및 단계 복잡성이 무엇인지 궁금해하고있었습니다.

내 지식에 따르면 정렬 작업의 복잡성은 O (NlogN)라고 생각합니다. 하지만 unique_by_key 작업에 대한 정보가 없습니다.

Answer 1

추력에는 두 가지 유형의 정렬이 있습니다. 기수 정렬과 비교 정렬이 있습니다. 기수 정렬의 경우 작업 복잡도는 O (kN)입니다. 여기서 N은 키의 수이고 k는 키 길이입니다. 비교를 위해, 언급 한대로 작업 복잡성은 O (N log N)입니다.

unique_by_key은 스트림 압축 작업이므로 작업 복잡도는 O (N)입니다.