エントリーの編集
![loading...](https://b.st-hatena.com/bdefb8944296a0957e54cebcfefc25c4dcff9f5f/images/v4/public/common/loading@2x.gif)
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
記事へのコメント1件
- 注目コメント
- 新着コメント
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
![アプリのスクリーンショット](https://b.st-hatena.com/bdefb8944296a0957e54cebcfefc25c4dcff9f5f/images/v4/public/entry/app-screenshot.png)
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
きまぐれ日記: ソートの平均要素移動距離
配列をソートする際に各要素の平均移動距離はどれくらいになるか問題が同僚の間で話題になった. 結論か... 配列をソートする際に各要素の平均移動距離はどれくらいになるか問題が同僚の間で話題になった. 結論から言ってしまえば,サイズ n の配列の場合平均移動距離は n/3 になるらしい. サイズ n の場合, 最右の要素は [0 .. n-1] に等確率で移動するので,直感的に考えると n/2 のような気がする.しかし,真ん中の要素は両側に移動するので,その距離は小さくなる.平均移動距離は n/2 より小さい値になるはずだ. 頭で考えるより手を動かしたほうが楽なので,モンテカルロサンプリングしてみた. 配列をランダムにシャッフルし,ソート済みの配列と比較して各要素の平均移動距離を求める.これを 1000 回繰り返し平均値を計算する. #include <iostream> #include <vector> #include <cmath> #include <algorithm> static
2007/02/08 リンク