エントリーの編集
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
Python3 平衡二分探索木は知らないがソートされた集合があったらいいなあって話 - Qiita
記事へのコメント0件
- 注目コメント
- 新着コメント
このエントリーにコメントしてみましょう。
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
Python3 平衡二分探索木は知らないがソートされた集合があったらいいなあって話 - Qiita
はじめに結論 Pythonのsetは集合の管理ができますが、要素にindexを持っていないので「小さい方からx番... はじめに結論 Pythonのsetは集合の管理ができますが、要素にindexを持っていないので「小さい方からx番目の要素を出力する」という操作を要素数 N に対して $O(N)$ でしか行えません。 あ〜遅すぎる。 結論を言うと、Binary Indexed Treeと二分探索で$O((logN)^2)$になります。もっと高速化できるかはよく知りません。 (4.13追記) Salmonize氏、joe氏ご指摘ありがとうございました。 $O((logN)^2)$としていますが、BIT上の二分探索を応用することで二分探索パートがBITのクエリ処理を必要としなくなり、$O(logN)$に高速化されます。 どんな理屈? Binary Indexed Tree(以下BIT)を用意しましょう。なに?BITを知らない? https://ja.wikipedia.org/wiki/フェニック木 xを集合に