-
- いいね！1
IT名著
@itmeicho
【来月発売・洋書】『Algorithm Design (2nd Edition) http://t.co/Vs6r5c7j 』 Jon Kleinberg による名著「アルゴリズムデザイン」の原著の第２版。2011年10月発売予定 #アルゴリズム
2011-09-17 21:42:56
集会の自由
@oskimura
7.2 クイックソートは例え分割が均等でなくてもオーダーはO(n lg n)となる #アルゴリズム勉強会 http://t.co/D4yIbbag
2011-09-23 15:00:27
集会の自由
@oskimura
第7.2 節の冒頭で主張したように漸化式T(n) =T(n-1)+Θ(n) の解がT(n) =Θ(n2 ) となることを，置換え法を用いて証明せよ. #アルゴリズム勉強会 http://t.co/D4yIbbag
2011-09-23 15:07:55
集会の自由
@oskimura
7.2-2 配列 A の要素がすべて同じ値であるとき, QUICKSORT の実行時間を評価せよ. #アルゴリズム勉強会 http://t.co/D4yIbbag
2011-09-23 15:33:08
集会の自由
@oskimura
quick sort は配列がn でサイズ n-l と 0 の部分配列で分割されるのが最悪の場合 #アルゴリズム勉強会 http://t.co/D4yIbbag
2011-09-23 15:36:02
集会の自由
@oskimura
7.2-2 n(n-1)/2 -1 でinsert sortと同じ #アルゴリズム勉強会 http://t.co/D4yIbbag
2011-09-23 15:39:02
集会の自由
@oskimura
http://t.co/Ctn4Rguq quick sortの平均計算時間をcoqで証明する論文 #アルゴリズム勉強会 http://t.co/D4yIbbag
2011-09-23 15:43:43
集会の自由
@oskimura
7.2-3 配列 A の要素がすべて異なり,すでに減少順でソートされているとき, QUICKSORT の実行時間がΘ(n^2) であることを示せ. #アルゴリズム勉強会 http://t.co/D4yIbbag
2011-09-23 15:47:59
集会の自由
@oskimura
7.2-4 時刻順を小切手番号順に変換する問題はほとんどソートされた入力をソートする問題であ る.この問題に対しては,手続き INSERTION-SORT が手続き QUICKSORT を論ぜよ. #アルゴリズム勉強会 http://t.co/D4yIbbag
2011-09-23 15:54:55
集会の自由
@oskimura
Insert sort は最良の場合Ω(n)であるが、QuickSortは最良でもlg n の高さで それぞれn/2回比較するので n lg n #アルゴリズム勉強会 http://t.co/D4yIbbag
2011-09-23 15:56:28
集会の自由
@oskimura
7.3-1 乱択アルゴリズムでは最悪時の性能ではなく平均時の性能を解析するのはなぜか? #アルゴリズム勉強会 http://t.co/D4yIbbag
2011-09-23 16:56:15
集会の自由
@oskimura
7.3-2 手続き RANDOMIZED-QUICKSORT 値を示せ . Θー記法を用いて答えよ. #アルゴリズム勉強会 http://t.co/D4yIbbag
2011-09-23 17:10:50
集会の自由
@oskimura
p149の１１行目のmax_1<=1<=n-1はmax_0<=1<=n-1の誤植？ #アルゴリズム勉強会 http://t.co/D4yIbbag
2011-09-23 17:30:39
集会の自由
@oskimura
7.4-1 漸化式 T(n) = max_n<=1<=n-1 (T(q) + T(n-q-1))+ Θ(n) の解が T(n) =n(n2) であることを示せ. #アルゴリズム勉強会 http://t.co/D4yIbbag
2011-09-23 17:36:26
集会の自由
@oskimura
7.4-2 クイックソートの最良時の実行時聞が n(nlgn) であることを示せ. #アルゴリズム勉強会 http://t.co/D4yIbbag
2011-09-23 18:02:27