ステップ数と計算量？

質問

ステップ数と計算量とは何でしょうか？
問題で、

int x = 0;
for(int c = 0; c < n; ++c)
a += c

との問題があり「これのステップ数と計算量をnについて求めよ。」との問題でした。
しかしステップ数と計算量というものがよくわかりません。
ステップ、つまり行数でいいのでしょうか？
計算量もO（オーダ）を使うどうのと一応知人から教わったのですが、
知人自体もよくわかっていないようで結局何なのだか・・・。

ステップ数と計算量というものについて教えてください。
あとできれば上記の問題についても・・・

回答No.1

hitomura · ベストアンサー

ややこしいことに処理を行う行数をステップ数と呼ぶ場合もあるのですが、
この場合のステップ数というのは何らかの処理を行った回数のことです。

あなたの場合では、

int x = 0;　　　　　　　　　　/* 変数 x の確保＆初期化 */
for(int c = 0; c < n; ++c) /* 変数 c の確保＆初期化 */
// （1）
　　　　　　　　　　　　　　　　/* c と n の比較 */
　　　　　　　　　　　　　　　　/* （2）へ処理を移す（前期条件を満たした場合のみ） */
　　　　　　　　　　　　　　　　/* c に 1 を加算 */
a += c　　　　　　　　　　　　/* a に c を加算 */
　　　　　　　　　　　　　　　　/* （1）へ処理を移す */
// （2）

という処理が行われます。人によっては「（*）へ処理を移す」を処理に含めない場合がありますし、「確保＆初期化」を2つの処理に分けるという考え方もあります。
あとは n という値が与えられたとき全体で処理が何回行われるかを数えてやればステップ数が計算できます。

で、おおざっぱにいうと、こうやって求めたステップ数が n の増え方と比較してどういう割合で増えるかを計算量といいます。
このとき、増え方が一番きついものを代表として採用し、n に関係しない値は無視します。
複数のアルゴリズムの効率を比較する場合、そっちの方が正確なステップ数を比較するよりわかりやすいからです。

え、問題の答？
上の処理を実際の値でいくつか試してみて、どういう風に各処理が行われるか（ここは毎回通るなとかここは 1 回だけだなとか）を調べるだけです。頑張ってください。

回答No.3

Yune-Kichi

とりあえず，計算量というか時間計算量について。

処理の実行時間が仮にf(n)で表すことができるとして，
nがある正数Nより大きい場合に常に|f(n)| ≦ M|g(n)|となる正定数Mとnの関数g(n)がある場合，その処理の計算量はΟ(g(n))であると言います。
通常，ランダウの記号で出てくるのはΟですが，|f(n)| ≧ M|g(n)|となるのであればΩ(g(n))，
M|g(n)| ≦ |f(n)|かつ|f(n)| ≦ M'|g(n)| (M'も正定数) であればΘ(g(n))と表記します。

言い換えると，nが無限大に漸近していくときの上界がΟ，下界がΩです。
# 両方が一致するのがΘ。

例題は，
・1行目：nに依存しない時間がかかる
・2行目：nに比例する時間がかかる
・3行目：nに依存しない時間がかかる
ため，全体としてはnに比例する時間がかかります。
つまり，f(n) = an + b (a, bは定数/aは正数)のように数式化されると仮定され，nが無限大に漸近していくと，
(a - 1)n < an + b < (a + 1)n
という関係が成り立ちます。
故に，Θ(n)と表記できます。
なので，Ο(n)であり，Ω(n)であり，Ο(n log n)であり，Ω(log n)であり……となります。

同様に，メモリをどれだけ使うか，という「空間計算量」というのもありますが，今回はΘ(1)なので省略します (nに依存しない)。

ステップというのは，「何回通るか」を意味する場合もあれば，「文の数」を意味する場合，「物理的な行の数」を意味する場合もあります。
最初の物をnについて数式化するとf(n)になるわけですが (各式の計算量を加味する必要はある)，
残りはそのまんまな，言語文法だったりファイルの物理構造だったりの問題になります。

回答No.2

TooManyBugs

ステップ数も計算量も明確な定義がありません。
使用する目的や要求者の思想によって変わってきます。

この場合だと教科書や授業で定義が明示されているのでなければ問題の答としては。

「定義されていないから回答不能」

です。