Skip to content

Week 3: 基本的なアルゴリズム

1. 探索アルゴリズム

配列やリストの要素を順番に調べていく最も基本的な探索方法。

特徴:

  • 単純で実装が容易
  • 小さなデータセットや未ソートのデータに適している
  • 時間複雑度: O(n)

Python での実装例:

1
2
3
4
5
def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # 見つかった場合、インデックスを返す
    return -1  # 見つからなかった場合

ソートされた配列やリストを半分ずつ絞り込んでいく効率的な探索方法。

特徴:

  • ソートされたデータセットに対して非常に効率的
  • 時間複雑度: O(log n)

Python での実装例:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid  # 見つかった場合、インデックスを返す
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1  # 見つからなかった場合

2. ソートアルゴリズム

2.1 バブルソート（Bubble Sort）

隣接する要素を比較し、必要に応じて交換を繰り返す単純なソート方法。

特徴:

  • 実装が非常に簡単
  • 小さなデータセットに適している
  • 時間複雑度: O(n^2)

Python での実装例:

1
2
3
4
5
6
7
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

2.2 選択ソート（Selection Sort）

最小（または最大）の要素を選択し、順に配置していくソート方法。

特徴:

  • 実装が比較的簡単
  • 小さなデータセットに適している
  • 時間複雑度: O(n^2)

Python での実装例:

1
2
3
4
5
6
7
8
9
def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

2.3 挿入ソート（Insertion Sort）

ソート済みの部分列に新しい要素を適切な位置に挿入していくソート方法。

特徴:

  • 小さなデータセットや部分的にソートされたデータに効果的
  • オンラインアルゴリズム（データを逐次的に処理可能）
  • 時間複雑度: O(n^2)

Python での実装例:

1
2
3
4
5
6
7
8
9
def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

3. 再帰の基本

再帰は、問題を小さな同種の問題に分割して解決する手法です。

特徴:

  • 複雑な問題を簡潔に表現できる
  • スタックオーバーフローの危険性がある
  • 終了条件（ベースケース）が重要

例: フィボナッチ数列の計算

1
2
3
4
5
def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)

4. 実践演習

4.1 探索アルゴリズムの比較

タスク: 線形探索と二分探索の性能を比較するプログラムを作成してください。

  1. 1から10000までの数字を含む配列を生成
  2. ランダムな数字を10個選び、各数字に対して両方の探索アルゴリズムを実行
  3. 各アルゴリズムの実行時間を測定し、比較結果を出力

4.2 ソートアルゴリズムの実装と比較

タスク: バブルソート、選択ソート、挿入ソートを実装し、性能を比較するプログラムを作成してください。

  1. ランダムな整数を含む配列を生成（例: 1000個の要素）
  2. 各ソートアルゴリズムを実行
  3. 各アルゴリズムの実行時間を測定し、比較結果を出力

4.3 再帰を使った問題解決

タスク: 以下の問題を再帰を使って解くプログラムを作成してください。

  1. 階乗の計算
  2. 配列の合計値の計算
  3. ハノイの塔の解法

5. まとめと次週への橋渡し

Week 3では、基本的なアルゴリズムについて学びました。探索アルゴリズム、ソートアルゴリズム、そして再帰の概念を理解し、実装することで、効率的なプログラム設計の基礎を身につけました。

次週（Week 4）では、コンピューターアーキテクチャとオペレーティングシステムの基礎について学びます。ハードウェアの基本構成、OSの役割、プログラムの実行プロセスなど、コンピューターの動作原理に関する知識を