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

少し前にquicksortの比較回数を推定する話を聞きました。n個の要素をquicksortする場合の比較回数の平均comp(n)は次の式で表せます。

comp(0) = 0
comp(n) = n-1 + averagek(comp(k)+comp(n-1-k))

想定しているクイックソートのコードはこんな感じです。

def qsort(elements):
  n = len(elements)
  i = random.randrange(len(elements))
  # pivot = elements[i]
  k = partition(elements, i)  # partition: needs n-1 comparison
  # k is the position of the pivot
  qsort(elements[0..k])  # comparison comp(k)
  qsort(elements[k+1..n])  # comparison comp(n-1-k)

計算すると、comp(n) ~ n log nという関係が出てきます。 randomized quicksortの計算量ですね。

普通のquicksortの比較回数

横軸をlog scaleであらわし、縦軸をNで割っています。なので直線になっていれば y ~ x log x です。

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