ステップキーで固有のスラストソートと推力の複雑さ

Question

推力のキー機能によってソートとユニークさを使用しています。私はちょうど推力のソート機能のステップの複雑さと、何がユニークなキー機能による作業とステップの複雑さであるのだろうと思っていました。

私の知るところでは、並べ替えの作業の複雑さはO（NlogN）だと思います。しかし、私はunique_by_key操作のためにそれが何であるか分かりません

Answer 1

推力には2種類の並べ替えがあります。基数ソートと比較ソートがあります。基数ソートの場合、作業の複雑さはO（kN）であり、Nは鍵の数であり、kは鍵の長さである。比較ソートでは、あなたが言及したように、作業の複雑さはO（N log N）です。

unique_by_keyは、作業の複雑さがO（N）であることを意味するストリーム圧縮作業です。