| Edit this page | Report an issue |
数列に含まれるk番目に大きな値を取得するアルゴリズムに関する問題。ピボットを使った再帰的な実装がクイックソートに似ている。
(2)は、アルゴリズムの計算量を求める問題。疑似コードの実装をもとに数学的に厳密な求め方をすると、とてもじゃないが試験時間内に解き終わらない。そこで、Pivot (p)が「平均的にAを２分割する」という事実を「常にpがAを２分割する」と認めてしまって計算することで、比較的容易に計算量のオーダーを求めることができる。
(1) は単純な計算問題。
(3) は見慣れない問題だが、問題で８つのキーが上手く設定されており、落ち着いて計算すれば連立方程式を解くだけの問題になる。
(2) での最適なハッシュ割り当ての論証は難しいが、(1)(3)は落としてはいけない問題である。
ナップサック問題に対して、貪欲法・動的計画法を用いる問題。
(1)(2) 計算問題
(3) 貪欲法の効率が悪くなるような問題設定を考える問題。（参考：リンク）
(4) 計算問題
(5) 有名な動的計画法の説明問題。アルゴリズムの知識がなくても場合分けをすれば解ける。ただし、時間内に解き終わるためには恐らく知識がないと厳しい。