週に一回は書きますよ 月に4つ記事を書けばノルマは満たされます。
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

配列をソートする際の各要素の平均移動距離が気になりました。N→∞でなら積分が使えて、全体の長さの1/3と求まります。 詳細はhttp://chasen.org/~taku/blog/archives/2007/02/post_822.htmlなど。

この値、正確にはN/3ではありません。たとえばN = 1ならソートする必要がないので移動距離は確実に0になります。N=2なら1/2になります。N/3としたときの誤差はどの程度あるのでしょう。

適当に計算したら正確な値が出ました。移動距離は(N2 - 1)/3N、全体の長さNで割ると 1/3 - 1/3N2になります。

予想より誤差が小さくて安心しました。ひょっとしてN/3 - 1とか、あるいはN/3 - √Nとかになるのではと心配していたので。

スポンサーサイト
コメント
この記事へのコメント
コメントを投稿する
URL:
Comment:
Pass:
秘密: 管理者にだけ表示を許可する
 
トラックバック
この記事のトラックバックURL
http://gusmachine.blog49.fc2.com/tb.php/428-0827bb80
この記事にトラックバックする(FC2ブログユーザー)
この記事へのトラックバック
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。