ステップ数と計算量とは何でしょうか?
問題で、
int x = 0;
for(int c = 0; c < n; ++c)
a += c
との問題があり「これのステップ数と計算量をnについて求めよ。」との問題でした。
しかしステップ数と計算量というものがよくわかりません。
ステップ、つまり行数でいいのでしょうか?
計算量もO(オーダ)を使うどうのと一応知人から教わったのですが、
知人自体もよくわかっていないようで結局何なのだか・・・。
ステップ数と計算量というものについて教えてください。
あとできれば上記の問題についても・・・
No.1ベストアンサー
- 回答日時:
ややこしいことに処理を行う行数をステップ数と呼ぶ場合もあるのですが、
この場合のステップ数というのは何らかの処理を行った回数のことです。
あなたの場合では、
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
- 回答日時:
とりあえず,計算量というか時間計算量について。
処理の実行時間が仮に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
- 回答日時:
ステップ数も計算量も明確な定義がありません。
使用する目的や要求者の思想によって変わってきます。
この場合だと教科書や授業で定義が明示されているのでなければ問題の答としては。
「定義されていないから回答不能」
です。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 計算機科学 判定問題がPに属するなら探索問題はNPに属する。では判定問題がNPに属するとき探索問題は? 2 2023/05/20 19:10
- 工学 【制御工学】単位ステップ応答の遅れ時間の求め方(令和2年度の機械設計技術者試験(制御工学)の問題) 3 2022/11/02 10:51
- C言語・C++・C# numpyスライス機能を使った数値計算 2 2023/05/08 16:01
- C言語・C++・C# C言語 3 2022/10/04 15:07
- その他(自然科学) 論文のまとめに関して(小論文)添削お願いします。 6 2023/07/16 14:24
- 工学 至急!!電流の瞬時値から実効値の求め方について 下記のExcelの画像のD列(黄色に塗りつぶしている 8 2022/06/29 19:00
- C言語・C++・C# このプログラミングの問題を教えてほしいです。 キーボードからデータ数nとn個のデータを入力し、平均値 3 2022/12/19 22:51
- 情報処理技術者・Microsoft認定資格 応用情報処理技術者試験のシステム利用率の計算について 2 2022/03/28 07:43
- 数学 高校時代電離平衡の計算に関しての質問です。 問題集で、 酢酸は水溶液中で一部が電離し、次のような電離 2 2022/10/22 18:59
- 数学 数学の問題の解説お願いします! 4 2022/08/28 05:22
このQ&Aを見た人はこんなQ&Aも見ています
関連するカテゴリからQ&Aを探す
おすすめ情報
このQ&Aを見た人がよく見るQ&A
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
65536は2の何乗なのでしょうか?
-
C言語の課題で、1年の秒数を計...
-
VBAの再計算が反映されない件に...
-
排他的論理和 BCC(水平パリテ...
-
変化させるセルが変化しない
-
Java 電卓の連続計算
-
C言語についてです。 再帰を使...
-
2進数の乗算をc言語で計算した...
-
C# 計算処理中に実行中ウィン...
-
加速度から変位の変換について
-
バッチファイルでウインドウを...
-
電卓でmodの計算
-
C言語のプログラミングの問題で...
-
先行評価と遅延評価
-
EXCELなどで「返す」という表現
-
VBA 九九 Do While
-
階乗のマクロ
-
太陽の位置計算のプログラムを...
-
行列計算の速度
-
VB.NETで16bit符号なしを使いたい
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
65536は2の何乗なのでしょうか?
-
VBAの再計算が反映されない件に...
-
排他的論理和 BCC(水平パリテ...
-
EXCELなどで「返す」という表現
-
バッチファイルでウインドウを...
-
モジュラス103の計算とは何でし...
-
傾いた四角形内の範囲の条件式
-
Visual C++でdebugとreleaseで...
-
変化させるセルが変化しない
-
骨折リスク評価のFRAXについて...
-
C# 計算処理中に実行中ウィン...
-
VBAでの勤務時間計算
-
べき乗の計算が遅い理由
-
C言語についてです。 再帰を使...
-
Excel VBAにてFFT
-
数値計算の高速化 (cos, sin, exp)
-
VBとVBAの違い
-
VB6で正確なミリ秒を計測したい...
-
スレッド処理からダイアログを...
-
matlabで計算終了
おすすめ情報