アルゴリズムとデータ構造 - プログラミングスレまとめ in VIP

計算量 † アルゴリズムがどれだけ効率的かを示す概念が計算量です。通常、単に計算量と述べた場合は、データ数nに対してどれだけ時間がかかるかを示す時間計算量を指しますが、場合によってはどれだけメモリを消費するかを示す空間計算量を問題にするケースもあります。計算量は、通常データ数nが十分大きい場合にnのどういう関数に比例して計算時間／メモリ消費が増えるかという形式で表します。 具体的に、下に述べている線形探索の例で計算量を考えてみましょう。この関数では、ループをサイズn回だけ回していますが、このループ1回辺り時間tだけかかるとしましょう。さらに、関数の呼び出し等により、データ数にかかわらず一定の時間sがかかると考えられます。従ってこの関数に費やす時間はnt+sですね。この時、十分大きいnを考え、かつ定数倍は無視して考えます。例えばntがsの10000倍だと仮定しましょう。この時sの寄与は、体重