基礎理論カテゴリの総まとめ。理解を得点につなげるための重要ポイントを再確認します。
日野 こむぎ
基礎理論、ぜんぶ学んだよ!
でも、ちょっと頭の中がごちゃごちゃかも…
藤森 さやか 先生
じゃあ最後に、頻出テーマを総ざらいしましょうか。
基礎理論は科目A・科目Bの両方で出題される中核分野ですからね。
青木 澪
まず数値表現: 2進数⇔10進数⇔16進数の変換は瞬時にできるように。
1バイト=8ビット=00〜FF。
これは科目Aで毎回出るわ。
桃井 すみれ
次は論理演算ですねぇ〜♪
青木 澪
そう、AND/OR/NOT/XORの真理値表は必ず暗記ね。
XORは「異なれば1、同じなら0」「2回かけると元に戻る」という性質も重要よ。
シフト演算は ×2/÷2 の高速化テクとして覚えておいて。
日野 こむぎ
データ構造とアルゴリズムはどうだっけ?
藤森 さやか 先生
配列(高速アクセス・遅い挿入)、リスト(逆)、スタック(LIFO)、キュー(FIFO)、木、ハッシュ。
それぞれの計算量を表で覚えるのがコツ。
青木 澪
ソートは: バブル・選択・挿入が O(n²)、クイック・マージ・ヒープが O(n log n)。
探索は線形 O(n)、二分 O(log n)、ハッシュ O(1)。
これも頻出ね。
桃井 すみれ
言語の分類も大事ですぅ〜。
コンパイラ型・インタプリタ型・JVMに、OOPの3要素、関数型の特徴…
藤森 さやか 先生
全部正解!
科目B (擬似言語) は基礎理論で学んだアルゴリズムの応用だから、ここをしっかり固めておけば擬似言語もちゃんと読めるようになるわ。
日野 こむぎ
よーし、これで自信もって基礎理論バッチリ押さえたぞ!
確認クイズ
次のうち、最も計算量が大きい (遅い) アルゴリズムはどれか。
- 配列のインデックスアクセス
- 二分探索 O(log n)
- クイックソート O(n log n)
- バブルソート O(n²)
こたえを見る
正解: 4. バブルソート O(n²)
計算量の比較: O(1) < O(log n) < O(n log n) < O(n²)。最も遅いのは バブルソート O(n²) です。基本ソートは小規模データでは十分ですが、大規模データには O(n log n) のソートを使うべきです。