再帰と分割統治法を用いたソートと選択アルゴリズムの実験
実験内容
1. ソートアルゴリズム
マージソート、クイックソート、ヒープソートを実装します。入力サイズ N は 8, 16, 32, 64, 128, 256, 512, … とし、1-1000 のランダムな整数を生成して入力データとします。実験結果を記録し、実行時間と入力サイズの関係をグラフにプロットします。各アルゴリズムの時間計算量と空間計算量を説明し、グラフを基に3つのソートアルゴリズ ...
7月22日 19:39 投稿
クイックソートの詳細解説
クイックソート（Quick Sort）はTony Hoareによって1960年に提案され、分治法を用いています。
分解：基準要素を選択し、配列を2つに分割します。
再帰：左右の部分配列を再帰的にソートします。
結合：部分配列が整列された後、全体が自然に整列されます。
基本的な実装例
#include <iostream>
#include <vector>
#include <algorithm>
class QS ...
7月3日 16:30 投稿
連続部分列の最大和を求めるときの主要3つのアルゴリズム
整数配列から和が最大となる連続した部分配列（要素は1つ以上）を見つけ、その和を返す問題を取り上げます。配列内の任意の連続する区間の合計値のうち最大値を求める手法として、漸化式を用いた線形走査、累積和の差分最適化、そして分割統治法を解説します。
手法1：漸化式による線形走査（Kadaneのアルゴリズム変形）
あるインデックス i で終了する連続部分配列の最大 ...
6月3日 22:26 投稿
最大部分配列問題の解法
最大部分配列問題
この記事では、最大部分配列問題の様々な解法について説明します。より詳細なアルゴリズムの考え方は「アルゴリズムイントロダクション」を参照してください。
部分配列構造体
typedef struct {
int start, end, total;
} SubArray;
力まかせ法による解法
すべての配列区間の和を計算して最大部分配列を見つける方法です。アルゴリズムの複雑さはθ( ...
5月30日 12:40 投稿