計算アルゴリズム【Ⅱ】
at TECH
[
2ch
|
▼Menu
]
■コピペモード
□
スレを通常表示
□
オプションモード
□このｽﾚｯﾄﾞのURL
■項目テキスト
300:デフォルトの名無しさん 06/02/11 18:45:05 >>298 いや、漏れが覚えている限りでは違うと思われ。 MITだかどっかの教科書の奴に載ってた。二番目を求めるけども一番最小を求めてからだったはず 院試にでてたかも。 301:デフォルトの名無しさん 06/02/11 18:57:23 >>300 やっぱり違ってた。考え直したら、 nが偶数なら (3/2)*n - 2, 奇数なら (3/2)*n - 3/2 回だった。 302:デフォルトの名無しさん 06/02/11 20:58:20 >>296 ソートアルゴリズムのところとかかな？学部生の時に必死こいてやったけどもう忘れた・・・。 あの教科書は原書で読んだ方がいいかもしれんな。英語だからかなりめんどくさいが。半期でやるのを英語でやったら一年半かかったよ。 303:デフォルトの名無しさん 06/02/12 00:24:16 証明になってないｗ 304:デフォルトの名無しさん 06/02/12 03:01:20 >>296 完全二分木でトーナメントを考えよう。 一番小さい要素を見つけるのにn-1回の比較が必要。 二番目に小さい要素は一番小さい要素の対戦相手のどれか。 木の高さはceil(log n)で木の一番上には対戦相手はいないから、 二番目に小さい要素の候補たりえるものはceil(log n)-1個 この中から一番小さいものをみつけるのにceil(log n)-2回の比較が必要。 したがって比較回数は、 (n-1)+ceil(log n)-2<n+logn-2 ただし、ceil(x)はxの小数点以下切り上げの関数
次ページ
最新レス表示
スレッドの検索
類似スレ一覧
話題のニュース
おまかせリスト
▼オプションを表示
レスジャンプ
mixiチェック！
Twitterに投稿
オプション
しおりを挟む
スレッドに書込
スレッドの一覧
暇つぶし2ch
4788日前に更新/251 KB
担当:undef