IT基礎・コンピュータ用語集

キーから値をほぼ一定の時間で引ける Java の連想配列。件数が増えても検索の速さを落とさずに対応表を扱うために使います。

ハッシュ表を使って重複のない集合を保つデータ構造。含まれるかどうかの判定が件数によらず速く、重複除去や既読の記録に向きます。

1つの根から枝分かれして広がる構造。データ構造としての木と、階層を表示する Linux の tree コマンドの両方で同じ形が出てきます。

問題を解く手順を、誰がなぞっても同じ結果になるように定めたもの。同じ答えを出す処理でも、手順しだいで所要時間が桁違いに変わります。

2 から順に倍数を消していき、消し残った数を素数として得る古典的な手法。範囲内の素数をまとめて求めるときの定番になります。

先に入れたものから先に取り出す、順番待ちの列そのままのデータ構造。届いた処理をためて順にさばく仕組みや、幅優先探索の土台になります。

基準値より小さい組と大きい組に分けることを繰り返して並べ替える手法。平均的に最も速い部類で、多くの言語の標準ソートの土台になっています。

点と線のつながりだけで対象を表すデータ構造。経路探索や関係の追跡に使い、路線図や友人関係のような循環のある関係を素直に扱えます。

処理を一本の流れだけで順に実行していく方式のこと。競合が起きない代わりに、重い計算を挟むと画面ごと止まってしまう点に注意します。

最後に入れたものを最初に取り出すデータ構造。積んだ順に戻る性質を使い、関数の呼び出し管理や取り消し操作、括弧の対応確認に使われます。

1 つのプロセスの中で並行して走る処理の単位。メモリを共有したまま同時に動くため、速さと引き換えに競合状態の管理が必要になります。

データをどう並べて保持するかを決める設計。選び方ひとつで検索や追加にかかる時間が桁で変わるため、処理速度の土台になる部分です。

任意の長さのデータから決まった長さの値を作る関数。同じ入力からは必ず同じ値が出る性質を使い、辞書の高速化や改ざん検知、パスワード保管に使われます。

隣り合う二つを比べて順序が逆なら入れ替える並べ替えの手法。速くはないものの動きが追いやすく、計算量を学ぶ入口になります。

最大値または最小値を根に保つ木構造。全体を並べ替えずに先頭の 1 個だけ即座に取れるので、優先度つきの処理に使われます。

入力が増えたとき処理時間やメモリがどう伸びるかを、定数を捨てて表す記法。アルゴリズムを実測せずに比べるための共通のものさしです。

0 か 1 のどちらかを表す情報の最小単位。8 個で 1 バイトになり、扱える数の範囲やファイルの大きさは、すべてこの個数から決まります。

画面からサーバー、データベースまで一人で通して作れる状態を指す言葉。機能を端から端まで動く形にするために求められる守備範囲を表します。

配列を半分ずつに分け、整列済みの列を併合して並べ替える手法。どんな並び順の入力でも速度が落ちず、同じ値どうしの順序も入れ替わりません。

実行中のプログラムとデータを一時的に置く高速な記憶領域。電源を切ると消えるため、残したいデータはディスクへ書き出します。

Gitで実際にファイルを編集している作業フォルダのこと。ここでの変更はまだ記録されておらず、addとcommitを経て履歴になります。

データが増えたときに処理時間やメモリがどう伸びるかを表す指標。手元の少ない件数では分からない性能の差を、実装する前に見積もるために使います。

関数が自分自身を呼び出して問題を小さく分けていく書き方。階層の深さが決まっていない木構造やフォルダの探索を短く表すために使います。

入力の件数が増えたとき処理時間がどう伸びるかを表す指標。O記法で書き、遅くなる処理を実装してしまう前に見当をつけるためのものさしです。

フローチャートで計算や代入といった一手順を表す長方形の記号。処理を四角、分岐をひし形と描き分けることで、書く前に手順の抜けを見つけられる。

先頭から順に1件ずつ照合して目的の要素を探す方法。並び替えも準備も要らないため、少ない件数や整列できないデータでは今でも最適な選択になります。

未整列の範囲から最小値を選んで先頭と入れ替える操作を繰り返す整列法。交換回数が少なく、仕組みが追いやすい入門向けの手法です。

整列済みのデータの中央と比べ、半分ずつ候補を捨てながら目的の値を探す方法。100万件でも20回ほどの比較で目的の位置にたどり着けます。

各ノードが子を最大2つまで持つ木構造。探索・整列・優先度つき取り出しを、データ量の対数に比例した手数で行うための土台になります。

大きな問題を同じ形の小さな問題へ割り、解いてから統合する設計手法。マージソートや二分探索など、速い定番アルゴリズムの骨格です。

ひとつの根から枝分かれし、親子関係で階層をつくるデータ構造。フォルダや DOM、組織図のような入れ子の関係を表すのに使います。