fixedpoint.jp

時間複雑性および空間複雑性がO(1)のソートアルゴリズム AC sort (2015-10-01)

入力: 集合Xの要素からなるリストL

出力: 並び換えるとLと等しい、ソートされたリスト

アルゴリズム:

• 選択公理(AC)を仮定する。
• 必要ならXに要素を追加して、一般性を失わずにXが十分大きい巨大基数(e.g. Reinhart cardinal)の濃度をもつとしてよい。ACよりXに整列順序が存在するが、これは矛盾[Kunen (1971)]。したがって「Lがソートされている」という命題が導ける。
• よって出力としてLを返す。

分析:

• 時間複雑性: O(1)
• 空間複雑性: O(1)

Intelligent Design Sort を参考にしました。