データ構造

【でーたこうぞう (data structure)】

与えられたデータを, 計算の高速化のために構造をもたせて記憶する手法の総称. 目的に合わせ, あるいくつかの機能を, 高速, あるいは省メモリで行えるよう設計される. 例えば, ある言葉を$n$ 個の言葉の辞書データから検索するとき, 通常の配列では, 最悪で挿入・削除に O$(n)$, 検索に O$(\log n)$ か, 挿入と削除に O$(1)$, 検索に O$(n)$ の時間を要する. 二分探索木というデータ構造は, これらの機能を O$(\log n)$ 時間で行い, 使用メモリは O$(n)$ である.