KDOC 484: 『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』

• 作成
  • <署名>

• レビュー
  • <署名>

『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』は、コンテストを題材にして基礎的なアルゴリズムを解説する本。

• アルゴリズムの効率は主に2つの計算量で評価される。このトレードオフを考えてアルゴリズムを設計する。時間計算量のほうが問題になることが多い(p43)
  • 時間計算量
  • 領域計算量
• 重要なことは、プログラムを実装する前に、入力の上限からアルゴリズムの最悪の計算量を評価すること(p45)
• ソートアルゴリズムの選択の基準(p53)
  • 計算量と安定性
  • データの列を保持する以外のメモリ
  • 入力データの特徴が計算量に影響しないか
• 選択ソートは離れた要素を交換するので安定なソートではない(p68)
• キューの実装方法の1つとして、headとtailのポインタを記録しておく方法がある。キューを処理するたびに先頭要素がずれていき、そのままではメモリを無駄にする。かといってheadを常に0に保つようにデータ全体移動させると、そのたびに要素長ぶんの計算が必要になる。ので、リングバッファにする方法がある(p90)

なし。