2010-02-06から1日間の記事一覧
線形時間ソーティング。比較ソートがnlognかかることの証明と、その結果を利用した別のアルゴリズムの計算量の下界の証明。obliviousなsort。 Exercise 8.1-1 n-1 Exercise 8.2-4 def exercise_8_2_4(a,k) n = a.length c = Array.new(k+1) for i in 0..k c[…
線形時間ソーティング。比較ソートがnlognかかることの証明と、その結果を利用した別のアルゴリズムの計算量の下界の証明。obliviousなsort。 Exercise 8.1-1 n-1 Exercise 8.2-4 def exercise_8_2_4(a,k) n = a.length c = Array.new(k+1) for i in 0..k c[…