PARKUDP今日はアルゴリズムの基本に加えて、コンピュータの心臓部・CPUについてもまとめてみるよ！
Qちゃんソフトとハードの両方をカバーするってことだね？
PARKUDPそうそう！試験は幅広いから、どちらも押さえておくのが大事なんだ。
目次
探索アルゴリズムとは
探索アルゴリズムとは、ある集合の中から目的のデータを見つけるための手順を定めたアルゴリズムです。
基本情報技術者試験では次の3つがよく出題されます。
- 線形探索法：先頭から順に比較して見つける方法
- ハッシュ法：データをハッシュ値に変換して高速に見つける方法
- 2分探索法：整列済みの配列を半分に分けながら探す方法
線形探索法
Qちゃん線形探索って一番シンプルなやつ？
PARKUDPうん。配列を先頭から1つずつ見ていくやり方だよ。準備は不要だけど、データが増えると遅くなるのが弱点。
特徴
- メリット：整列していなくても使える。準備が不要。
- デメリット：データ数が多いと処理時間がかかる。
- 使いどころ：データ件数が少ない場合や、一度きりの探索。
Python例
def linear_search(arr, target):
for i, x in enumerate(arr):
if x == target:
return i
return -1
data = [42, 7, 19, 100]
print(linear_search(data, 7)) # => 1
print(linear_search(data, 999)) # => -1ハッシュ法
Qちゃんハッシュ法って、Pythonの辞書と同じ仕組み？
PARKUDPその通り！キーをハッシュ関数で数値に変換して、その位置にデータを格納するんだ。平均するとすごく速いよ。
特徴
- メリット：平均すると探索はほぼ一発で済む。
- デメリット：異なるデータが同じハッシュ値になる「衝突」が起きることがある。
- 使いどころ：大量のデータを何度も検索する場合。
Pythonの辞書型（dict）例
phonebook = {"alice": "090-1234-5678", "bob": "080-5555-0000"}
print(phonebook["alice"]) # => 090-1234-5678
print("carol" in phonebook) # => False簡単なハッシュテーブル実装例（連鎖法）
class HashTable:
def __init__(self, m=8):
self.m = m
self.buckets = [[] for _ in range(m)]
def _hash(self, key):
return hash(key) % self.m
def put(self, key, value):
i = self._hash(key)
for idx, (k, v) in enumerate(self.buckets[i]):
if k == key:
self.buckets[i][idx] = (key, value)
return
self.buckets[i].append((key, value))
def get(self, key, default=None):
i = self._hash(key)
for k, v in self.buckets[i]:
if k == key:
return v
return default
ht = HashTable()
ht.put("alice", "090")
ht.put("bob", "080")
print(ht.get("alice")) # => "090"2分探索法
Qちゃん2分探索って、データが整列されてないと使えないんだよね？
PARKUDPそのとおり！整列済みなら「範囲を半分に絞る」ことができるから、すごく効率がいいんだ。
特徴
- メリット：探索回数が少なくて済む（O(log n)）。
- デメリット：事前にデータを整列させる必要がある。
- 使いどころ：同じデータ集合に対して何度も探索する場合。
Python例
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
sorted_data = [1, 3, 5, 7, 9]
print(binary_search(sorted_data, 7)) # => 3
print(binary_search(sorted_data, 6)) # => -1再帰的アルゴリズム
Qちゃん再帰って難しそう…自分で自分を呼ぶんだよね？
PARKUDPそうそう！ポイントは「小さく分ける」「必ず終わる条件を用意する」この2つ。試験では総和・mod・階乗あたりがよく出るよ。
例1：総和（1からnまでの合計）
def sum_1_to_n(n):
if n == 0:
return 0
return n + sum_1_to_n(n - 1)
print(sum_1_to_n(5)) # => 15例2：最大公約数（ユークリッドの互除法）
def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)
print(gcd(54, 24)) # => 6例3：階乗
def factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1)
print(factorial(4)) # => 24CPUの性能指標
Qちゃんところで、ハードウェア分野も出題されるんだよね？CPUってどう理解すればいいの？
PARKUDPCPUはコンピュータの「脳」みたいな存在。性能を示す3つの指標を覚えておこう！
クロック周波数
- 定義：CPUが1秒間に処理できるテンポの数
- 単位：Hz（ヘルツ）、1GHz = 10⁹回/秒
- クロック数：命令を処理するのに必要なクロックの数
- 公式：命令数 = クロック周波数 ÷ (1命令あたりのクロック数)
Qちゃんクロックが高いほど速い？
PARKUDP基本的にはそうだけど、命令の種類やCPUの設計でも処理時間は変わるよ。
MIPS（Million Instructions Per Second）
- 定義：1秒間に何百万命令を実行できるかを表す指標
- 式：MIPS = 1 ÷ 平均命令実行時間 × 10^-6
- 例：3MIPS = 1秒間に300万命令を処理
QちゃんMIPSだけで性能比較できる？
PARKUDP簡単な目安にはなるけど、実際は命令の内容や効率によって変わるから注意が必要なんだ。
コア数
- 定義：CPUの中にある処理ユニット（演算装置）の数
- 種類：デュアルコア（2コア）、クアッドコア（4コア）、それ以上もある
- 特徴：マルチタスクや並列処理に強い
- 注意：アプリがマルチコア対応していないと性能を発揮できない場合もある
Qちゃんコアが多いほど無条件で速い？
PARKUDP基本的には速いけど、ソフトウェアの対応が大事。試験では「コアが増えると並列処理が可能」と覚えておけば十分！
まとめ
今回のポイントを整理すると、次の3つのテーマに分けて覚えておくと理解が深まります。
| テーマ | アルゴリズム/概念 | 特徴 | 計算量 |
|---|---|---|---|
| 探索アルゴリズム | 線形探索 | 先頭から順に調べる。整列不要。 | O(n) |
| ハッシュ法 | ハッシュ値で直接アクセス。衝突あり。 | 平均 O(1)、最悪 O(n) | |
| 2分探索 | 整列済み配列を半分に絞る。効率的。 | O(log n) | |
| 再帰 | 総和（1～n） | 自分自身を呼び出して小さく分割。 | O(n) |
| 最大公約数 | b=0になるまで再帰。試験頻出。 | O(log n) | |
| 階乗 | n! を再帰で定義。 | O(n) | |
| CPU性能 | クロック周波数 | 1秒間の処理テンポ。高いほど速い。 | — |
| MIPS | 1秒間の百万命令数。比較指標。 | — | |
| コア数 | 処理ユニット数。並列処理能力に直結。 | — |
探索アルゴリズム
探索アルゴリズムには 線形探索・ハッシュ法・2分探索 の3種類があり、それぞれに適した場面があります。
- 線形探索：順番にすべて調べるシンプルな方法。小規模なデータに向いている。
- ハッシュ法：ハッシュ関数でデータの位置を直接求める方法。平均すると高速だが、衝突処理が必要。
- 2分探索：整列済みデータを対象に、範囲を半分に絞りながら探す方法。大量データに有効。
試験問題では「整列済み」と書かれていれば2分探索、「ハッシュ表」と書かれていればハッシュ法を使う、という判断パターンを覚えておくと良いです。
再帰的アルゴリズム
再帰的アルゴリズムは 自分自身を呼び出す処理 であり、次の3点が理解のカギです。
- 止まる条件（ベースケース） があること
- 問題を 小さな部分問題に分割 できること
- 部分問題の結果を 組み合わせて解を作る こと
典型的な出題例は「総和」「最大公約数（modを利用）」「階乗」など。特にユークリッドの互除法は試験に頻出です。
CPUの性能指標
CPUはコンピュータの「脳」であり、その性能は主に クロック周波数・MIPS・コア数 の3つで評価されます。
- クロック周波数：1秒間に処理できるテンポの速さ。数値が大きいほど基本的に速い。
- MIPS：1秒間に何百万命令を処理できるかを表す。性能比較に使われる。
- コア数：CPU内の演算装置の数。マルチコア化により並列処理能力が向上する。
これらの指標を組み合わせて理解することで、「CPUはただクロックが速ければいいわけではない」ことも見えてきます。
Qちゃんまとめを読んだだけでも、だいたい試験に出るポイントが思い出せるね！
PARKUDPその感覚が大事！次回はCPUが実際に命令を処理する流れを見ていこう！
コメント