Шаг Сложность сортировки тяги и тяги, уникальной по ключу

Question

Я использую сортировку и уникальные ключевые функции в тяге. Мне просто интересно, какова сложность шага функции сортировки в толчке и какова сложность работы и шага уникальной ключевой функции.

Исходя из моих знаний, я считаю, что сложность сортировки составляет O (NlogN). Но я понятия не имею, что это за операция unique_by_key

Answer 1

В Thrust есть два типа сортировки. Существует радикальная сортировка и сравнительная сортировка. Для радикальной сортировки сложность работы составляет O (kN), где N - количество ключей, а k - длина ключа. Для сравнения, сложность работы O (N log N), как вы упомянули.

unique_by_key - операция сжатия потока, что означает, что сложность работы составляет O (N).