Wikibooks

プログラミング/アルゴリズム

< プログラミング

アルゴリズムとは

編集

アルゴリズムは、特定の問題を解決するための明確で有限の手順セットです。計算機科学の基礎となる概念で、効率的なデータ処理と問題解決の鍵となります。

アルゴリズムの基本要素

編集
  1. 入力
  2. 出力
  3. 明確さ
  4. 有限性
  5. 効率性

基本的なアルゴリズムパターン

編集

探索アルゴリズム

編集

線形探索

編集
Ruby
def linear_search(array, target)
  array.each_with_index do |element, index|
    return index if element == target
  end
  -1
end

numbers = [4, 2, 7, 1, 5, 3]
puts linear_search(numbers, 7)  # 出力: 2
Go
func linearSearch(arr []int, target int) int {
    for i, value := range arr {
        if value == target {
            return i
        }
    }
    return -1
}

二分探索

編集
Ruby
def binary_search(array, target)
  left = 0
  right = array.length - 1

  while left <= right
    mid = (left + right) / 2
    
    return mid if array[mid] == target
    
    if array[mid] < target
      left = mid + 1
    else
      right = mid - 1
    end
  end

  -1
end

sorted_numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9]
puts binary_search(sorted_numbers, 7)  # 出力: 6
Rust
fn binary_search(arr: &[i32], target: i32) -> Option<usize> {
    let mut left = 0;
    let mut right = arr.len() - 1;

    while left <= right {
        let mid = left + (right - left) / 2;
        
        if arr[mid] == target {
            return Some(mid);
        }
        
        if arr[mid] < target {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    None
}

ソートアルゴリズム

編集

バブルソート

編集
Ruby
def bubble_sort(array)
  n = array.length
  
  (0...n-1).each do |i|
    (0...n-i-1).each do |j|
      if array[j] > array[j+1]
        array[j], array[j+1] = array[j+1], array[j]
      end
    end
  end

  array
end

numbers = [64, 34, 25, 12, 22, 11, 90]
puts bubble_sort(numbers).inspect
Go
func bubbleSort(arr []int) []int {
    n := len(arr)
    for i := 0; i < n-1; i++ {
        for j := 0; j < n-i-1; j++ {
            if arr[j] > arr[j+1] {
                arr[j], arr[j+1] = arr[j+1], arr[j]
            }
        }
    }
    return arr
}

マージソート

編集
Ruby
def merge_sort(array)
  return array if array.length <= 1
  
  mid = array.length / 2
  left = merge_sort(array[0...mid])
  right = merge_sort(array[mid..-1])
  
  merge(left, right)
end

def merge(left, right)
  result = []
  
  until left.empty? || right.empty?
    if left.first <= right.first
      result << left.shift
    else
      result << right.shift
    end
  end
  
  result.concat(left).concat(right)
end

numbers = [38, 27, 43, 3, 9, 82, 10]
puts merge_sort(numbers).inspect
Rust
fn merge_sort(arr: &mut [i32]) {
    if arr.len() <= 1 {
        return;
    }
    
    let mid = arr.len() / 2;
    merge_sort(&mut arr[..mid]);
    merge_sort(&mut arr[mid..]);
    
    merge(arr, mid);
}

fn merge(arr: &mut [i32], mid: usize) {
    let left = arr[..mid].to_vec();
    let right = arr[mid..].to_vec();
    
    let mut i = 0;
    let mut j = 0;
    let mut k = 0;
    
    while i < left.len() && j < right.len() {
        if left[i] <= right[j] {
            arr[k] = left[i];
            i += 1;
        } else {
            arr[k] = right[j];
            j += 1;
        }
        k += 1;
    }
    
    while i < left.len() {
        arr[k] = left[i];
        i += 1;
        k += 1;
    }
    
    while j < right.len() {
        arr[k] = right[j];
        j += 1;
        k += 1;
    }
}

グラフアルゴリズム

編集

深さ優先探索（DFS）

編集
Ruby
class Graph
  def initialize
    @graph = {}
  end
  
  def add_edge(node, neighbor)
    @graph[node] ||= []
    @graph[node] << neighbor
  end
  
  def dfs(start_node)
    visited = Set.new
    result = []
    
    dfs_recursive(start_node, visited, result)
    
    result
  end
  
  private
  
  def dfs_recursive(node, visited, result)
    return if visited.include?(node)
    
    visited.add(node)
    result << node
    
    @graph[node]&.each do |neighbor|
      dfs_recursive(neighbor, visited, result)
    end
  end
end

graph = Graph.new
graph.add_edge('A', 'B')
graph.add_edge('A', 'C')
graph.add_edge('B', 'D')
puts graph.dfs('A').inspect

計算量解析

編集

Big O 記法

編集 
# O(1) 定数時間
def constant_time_operation(arr)
  arr[0]
end

# O(n) 線形時間
def linear_search(arr, target)
  arr.each do |element|
    return true if element == target
  end
  false
end

# O(n^2) 二次時間
def nested_loop_operation(arr)
  arr.each do |x|
    arr.each do |y|
      # 何らかの操作
    end
  end
end

# O(log n) 対数時間
def binary_search(arr, target)
  # 二分探索のアルゴリズム
end

アルゴリズム設計のテクニック

編集
  1. 分割統治法
  2. 貪欲法
  3. 動的計画法
  4. バックトラッキング

実践的なアドバイス

編集
  • アルゴリズムの選択は問題の性質による
  • 時間計算量と空間計算量のトレードオフを理解する
  • 標準ライブラリの実装を活用する
  • 実際のデータで性能を測定する

まとめ

編集

アルゴリズムは、コンピュータサイエンスの中心的な概念であり、効率的な問題解決の鍵となります。様々な言語と手法を理解することで、より洗練されたソリューションを設計できます。

学習ロードマップ

編集
  1. 基本的なアルゴリズムパターンの理解
  2. 計算量解析の基礎
  3. 異なる言語でのアルゴリズム実装
  4. 実際の問題への応用
  5. アルゴリズムデザインパターンの習得
"https://ja.wikibooks.org/w/index.php?title=プログラミング/アルゴリズム&oldid=264281" より作成