QRcode to hig3.net
携帯キャリア自動判別
http://hig3.net

楽してトランプをそろえよう --- アルゴリズムと計算量

使える数学!(2010年度)
Time-stamp: "2009-10-28 Wed 07:47 JST hig"

担当教員による追加資料などを提供するサポートサイトです.

目次

  1. バブルソート
  2. いろんなソート
  3. もっと速いソート
  4. もっともっと速いソート
  5. 理論と現実は違う

追加情報

参考文献

下にいくほど難しくなります.

バーリンスキはアルゴリズムの考え方と意味を非専門家向けに述べた本, アンクは, C言語など何らかのプログラミング言語がある程度わかる方にソートアルゴリズムなどの考え方を説明したもの, セジウィックは, C言語がかなりわかる方に, 種々のソートアルゴリズムの性能や特徴を比較して説明したもの. セジウィックには, C++など他の言語を用いて同様の内容を述べた, さまざまな装丁のバージョンがあります.

  1. デイヴィッド バーリンスキ, 史上最大の発明アルゴリズム―現代社会を造りあげた根本原理,早川書房,2001.
  2. アンク, アルゴリズムの絵本-プログラミングが好きになる9つの扉,翔泳社,2003.
  3. R. セジウィック, アルゴリズムC〈第1巻〉基礎・整列,近代科学社,19963.

訂正と後悔

バブルソート-5(10:20)
[訂正] 「anとan-1を比較して…」と言っていますが, 正しくは「knとkn-1を比較して…」です. 比較するのはキーの値の大小(順序)です.
いろんなソート-4(04:54)
[訂正]スライドで, 「c入替(n-1)」とあるのは, 音声でも訂正している通り, 「c入替n」が正しいです. また, これは「山」がリンクトリストなどで実装されていて, どの位置への挿入に1単位の時間しかかからない場合です. 単純な配列で実装されている場合にはn2くらいになります.
理論と現実は違う-1(1:20)
[訂正]O(n?1)と発音していますが, O(1)と言うべきでした. O(nk)でk=0とおいたO(1)のことです.
理論と現実は違う-2,3,4
[補足]明示的に述べていませんが, この話ではnは商品の個数です.

確認テスト略解

確認テスト略解
Copyright © 2007-2010 Saburo Higuchi. All rights reserved.
樋口三郎, hig's mail address