プチコン 非公式コミュニティ
プレイ日記
こういち
◆.Id/aHiU36hu
2021/4/13 22:28
2021/4/13 22:28
スーさんの「アルゴリ」にソートアルゴリズム追加しようと思っていろいろ調べてたら二分ヒープのpushが平均O(1)という記述を見つけて驚いてる。速いわけだ…
ついでに、derease-key(値の優先度を上昇させる)も出来ると知ってさらに驚き。(正直decrease-keyの使いどころないと思ってたけど、工夫すればダイクストラ法で使えるんですね。)
ついでに、derease-key(値の優先度を上昇させる)も出来ると知ってさらに驚き。(正直decrease-keyの使いどころないと思ってたけど、工夫すればダイクストラ法で使えるんですね。)
コメント
こういち
2021/4/14 12:04
◆.Id/aHiU36hu
直感的に理解しづらいな…
少し解析してみよう。
swap回数の期待値がヒープのサイズに関わらず定数になれば平均定数時間と言える。
つまり、
Σ(n/(2^n))の無限級数が収束すればO(1)
無限級数の収束判定なんて久しぶりだよ…(数学の教科書を探す)
少し解析してみよう。
swap回数の期待値がヒープのサイズに関わらず定数になれば平均定数時間と言える。
つまり、
Σ(n/(2^n))の無限級数が収束すればO(1)
無限級数の収束判定なんて久しぶりだよ…(数学の教科書を探す)
こういち
2021/4/14 12:29
◆.Id/aHiU36hu
Σn^-2は収束することが知られているので、Σ(n/(2^n))も収束します。(雑)
さすらいの名無し
2021/4/15 18:57
◆LWMA5UzCJb3e
何言ってるのか何一つ理解できなかった()
こういち
2021/4/16 18:26
◆.Id/aHiU36hu
さすらいの名無しさん
役に立つか分かりませんが、一応解説を
ヒープ:データを追加する、追加したデータから最も小さいものを取り出す、といった操作が出来るデータ構造。
push:データ構造にデータを追加する。
O(1):定数時間。ヒープに入ってるデータの量に関わらず常に一定の時間で操作が完了する。
decrease-key:ヒープに入ってるデータの値を変更する
ダイクストラ法:最短経路を求めるアルゴリズム。ヒープを使うと距離が近い順に添削できるので速い。
役に立つか分かりませんが、一応解説を
ヒープ:データを追加する、追加したデータから最も小さいものを取り出す、といった操作が出来るデータ構造。
push:データ構造にデータを追加する。
O(1):定数時間。ヒープに入ってるデータの量に関わらず常に一定の時間で操作が完了する。
decrease-key:ヒープに入ってるデータの値を変更する
ダイクストラ法:最短経路を求めるアルゴリズム。ヒープを使うと距離が近い順に添削できるので速い。
こういち
2021/4/16 18:36
◆.Id/aHiU36hu
swap:値を交換する。二分ヒープはデータの追加、削除のたびにswapを繰り返すことで常に配列の0要素目に最小値が来るようになってる。
期待値:ランダムにデータが入ってると仮定した場合の平均的に期待できる回数
Σ:for文。中の変数(この場合n)をある値(この場合無限大)まで1づつ増やした場合の合計。
無限級数:ある式を無限に足しあわせていったもの。
収束:ある値に落ち着くこと。
知られている:先人が既に証明していること。
期待値:ランダムにデータが入ってると仮定した場合の平均的に期待できる回数
Σ:for文。中の変数(この場合n)をある値(この場合無限大)まで1づつ増やした場合の合計。
無限級数:ある式を無限に足しあわせていったもの。
収束:ある値に落ち着くこと。
知られている:先人が既に証明していること。
コメントを書く
- こちらは「プチコン3号」「プチコンBIG」など、プチコンシリーズに関する話題を扱ったコミュニティです
- プチコンシリーズにまったく関係ない書き込みはご遠慮下さい。削除の対象となります
- こちらにはその他のゲームや雑談のコミュニティはなく、作る予定もありません (ひとりで管理できないため)。ごめんなさい
- ユーザー登録なしで書き込みができます
- 秘密の合い言葉は成りすましの防止 (トリップ機能)、書き込みの編集時の本人認証に使用します
- 秘密の合い言葉に他人に推測されやすい言葉、他サービスと同じパスワードは入力しないでください。
- 書き込むと、投稿時に入力したお名前と秘密の暗号が記憶され、ログイン状態になります