こんにちは、c#初心者です。
今回は計算量オーダーの話なので、基本的に言語は関係ないと思います。
計算量オーダーの基本的な部分は分かるのですが、O(1/n)オーダーのアルゴリズムは(今のところは)まだ見かけないというか、名前程度しか知らないので、これに関しては無知です。そこで、この場合はどういうオーダーになっているのかという質問です。
質問は3つあります。
1)この一連の処理はO(1/n)オーダーになっているか?
int count = 1000 / length; // lengthは正の整数
for ( int i = 0; i < count; i++ ) Do(); // O(1)オーダーの処理
2) (1がO(1/n)の場合)繰り返す処理がO(n^2)になった場合に、この一連の処理はO(n)オーダーになるのか?
int count = 1000 / length; // lengthは正の整数
for ( int i = 0; i < count; i++ ) Do(); // O(n^2)オーダーの処理
3)配列型のコレクション(コレクションって、c#の呼び方だったっけ?) [c#] List<T>,[c++] Bector, [Java] ArrayList(だったっけ?)のようなクラスのAddメソッドのオーダーは?
//Addメソッドの中身
if ( Capacity == Count ) Expand(); // Expandは配列の容量を2倍に拡張するO(n)処理とします。
array[Count++] = item;
以上です。
補足で、2)については大学の教授に「一回でもO(n^2)の処理が呼び出されたら、O(n^2)オーダーになる」と言われましたが、納得いかないです。確かに、O(1/n)オーダーの処理の後にO(n^2)オーダーの処理を行えば、そうなるのは納得いくのですが……という感じです。教授が読み間違えたとは考えにくいですが(確かにちょっと忙しそうでしたが)、念のため質問です。
それと、3)はよくある配列型のコレクションのまねです。「もし内容物が容量一杯になれば拡張→追加」を繰り返すとした場合です。ExpandメソッドのオーダーがO(n)なので、単純に計算すればO(n)オーダーになるのですが、呼び出される頻度が「(拡張された容量)回に1回」です。
例えば、容量が4ずつ拡張されるとすれば、「4回に1回」拡張が必要になり、10ずつ拡張されるとすれば、「10回に1回」の拡張が必要です。この場合、どう考えても全体として定数で割っているだけなので、O(n)オーダーのままになるのは明白なのですが、今回は容量2倍とさせていただきました。すると拡張の頻度は「(さっきまでの容量)回に1回」の頻度で、容量に反比例し、直感的にはO(Count / Capacity) = O(1)オーダーに見えるのですが、この判断は正しいでしょうか?
皆さんのご意見を伺わせてください。
No.6ベストアンサー
- 回答日時:
えぇっと....
x * y ≦O(max{x, y}^2) って書かれると, 今度は「その不等号って何?」ってなっちゃうんだよね. = を使えば問題ないのに, 逆に怪しい不等号をなんでわざわざ使っちゃうかなぁ.
この回答への補足
ああ、書き間違いです。多分x * y = O(max{x, y})とx * y ≦ max{x, y}が単に混ざっただけかと(さすがに、分かってらっしゃったとは思うんですけれどね、文脈から)。
補足日時:2012/10/08 08:28 O(xy)なんかをO(n^2)のように簡素化して、shortの列挙体で表そうと思っていましたが、諦めてlongの列挙体 使います。
回答ありがとうございました。
No.5
- 回答日時:
最初から「x と y の大きい方を n とする」といっておけばいいんだけどねぇ. ただ, 「x と y の大きい方を n とする」といった時点で「x, y, nは互いに独立」とは言わない.
オーダーの定義はちょっと違うのできちんと確認しておくこと.
ご指摘ありがとうございます。
そういえばそうですね。あんまりその辺は気にした事がなかったので(今思えば、いつも、こんな大雑把な思考しかしてないですね。だから、こんな質問ばかりしているのか。よく今まで来れたもんだと自分でも驚く)。
そういえば、オーダーの定義には絶対値になっていたような。あと、x0と、cにももう少し規制があったような(少なくとも1つは存在するだったかな?)……。
それで、本題なのですが、結局は、x * y ≦O(max{x, y}^2)にはならないってことですか?
No.4
- 回答日時:
x や y と n が関係ないのなら, ますます
x * y = O(n^2)
などと書くことはできません. オーダーの意味, 理解してる?
ご指摘ありがとうございます。
理解していると言えるかどうか分かりませんが、アルゴリズムの速度の指標ですよね。どの程度の速度で計算量が成長していくかを大まかに示した。
プリントをなくしてしまったので、細かい部分は忘れましたが、
f(x)がO(g(x))オーダーであるとは、
x0 < x で、 f(x) < c * g(x) cは任意の正の実数?
だったような。
それで、nは任意なので、例えばx, yの大きい方をnにすれば、x * y≦n^2になるので、最大時間計算量をを考える場合、x * y = O(n^2)になるかと勝手に思っていました。
x + yも、例えば大きい方をnとすれば、x + y≦ 2nで、2はcに吸収してやれば、x + y ≦ cnになるので、x + y = O(n)になると思っていました。
1つ抜けていましたが、x, yは少なくとも負でない実数で、の変域は一緒です。まあ、分布が異なれば意味が無いような気もしますが。
No.3
- 回答日時:
#2 へのお礼の最後のところだけ... なんだけど....
#1 に
「n が何を意味するのか」ってところから始めないとダメ
って書いておいたんだけど, 理解できてます? x や y と n の関係, どこにも書いてないよ.
ご指摘ありがとうございます。
どの程度の理解が求められているのか分かりませんが……。とりあえず、x, y, nは互いに独立した任意の変数です(な訳で、関係書いていませんでした。ひょっとしたら、nはx, yの平均の方が良いのかもしれませんが)。
例えば、[x, y]のサイズの2次元配列があったとして、この配列を拡張やコピーする場合です。この場合、O(x * y)オーダーになると思いますが、どちらも(x→∞), (y→∞)として考えるのであれば、他の変数nを用意して、(n→∞)で大雑把にO(n^2)とみなす事は出来るのか? という事を質問したかったわけです。
No.2
- 回答日時:
(1)について
> int count = 1000 / length;
lengthに依存しない時間がかかるのでΟ(1)
> for ( int i = 0; i < count; i++ ) Do(); // O(1)オーダーの処理
length≧1000でcountは常に0,つまり「定数時間がかかる」のでΟ(1)
故に,全体でΟ(1)
(2)について
Doのオーダーがなんであれ,通常Οは∞近傍の話ですから,定数時間がかかる,つまりはΟ(1)です。
Ο(1)はΟ(n)でもあるので間違いではありませんが……。
(3)について
今回はΘを論ずるのではなくΟを論じていますから,
List<T>.Addやvector<T>.push_back,ArrayList<T>.addはΟ(n)といっても間違いではありません。
Οはn→∞で「計算量は~(の定数倍)以下である」と言っているのですから,「定数であるかnに比例する計算量」であるこれらのメソッド/関数は,「nに比例する計算量以下」の計算量である,と言ってしまうことが出来ます。
# 「Ω(1)でΟ(n)」かつ「Ω(log n)ではなくΟ(log n)ではない」,「Θでは表記不可」,かなぁ。
次に,(2)に対する補足について。
まず,f(n)∈Ο(1),g(n)∈Ο(n * n)の場合,Οの定義からn→∞でf(n)の計算量はC以下,g(n)の計算量はD * n * n以下となります。
この時,D ≪ EとなるEを選べば,n→∞においてf(n) + g(n)の計算量 ≦ C + D * n * n ≦ E * n * nが成立します。
よって,f(n) + g(n)の計算量はn→∞においてE * n * n以下,つまりはΟ(n * n)となります。
一般化して,
f(n)∈Ο(F(n)), g(n)∈Ο(G(n))について,n→∞において,
・f(n)の計算量 ≦ Mf * F(n)
・g(n)の計算量 ≦ Mg * G(n)
・f(n)+g(n)の計算量 ≦ Mf * F(n)+Mg * G(n) ≦ M * MAX(F(n),G(n)) ただし Mf, Mg≪M
∴f(n)+g(n)∈Ο(MAX(F(n), G(n)))
・f(n) * g(n)の計算量 < Mf * F(n) * Mg * G(n) = (Mf * Mg) * (F(n) * G(n))
∴f(n) * g(n)∈Ο(F(n) * G(n))
です。
# Mf, Mg, Mは定数,MAX(F(n), G(n))はF(n)とG(n)のn→∞での小さくない方の式
回答ありがとうございます。
納得しました。ありがとうございます。
それと、ΩにΘ、良く分からなかったので調べてみました。意味は分かったのですが、3)のような場合で、例えばさらに2次元配列(とりあえず、長方ではなく正方形とします)のクラスを想定するとAddメソッドは、Ω(1)、O(n^2)になると思いますが、実際の平均はO(n)になりますよね?
この場合、ΩとOのどちらを見ても平均がO(n)である事にはたどり着けないので、メソッドの(何度も呼び出した場合の)平均の(ならし?)計算量も説明(概要か詳細)に加えていたほうがよいでしょうか? (特にライブラリのような場合)
その場合、O-記法を使っても良いのでしょうか?
と、大事なことを忘れていました。いまさらなのですが、x, yは変数として、 x * y = O(n^2)と見ることは出来るのでしょうか? それとも、O(x * y)のように記述するのでしょうか?
No.1
- 回答日時:
1) はそもそも count を計算するために O(1) 必要では? まあ, 「n が何を意味するのか」ってところから始めないとダメだけど, ね.
3) は... まず, 「1回追加するのに O(1)」とはいえないことはいいね? もちろん「n回追加すると O(n)」だから, 「平均すると」 O(1) とはいえる. ただ, これは単純な計算量ではなく, amortized complexity (ならし計算量) とか言ったりすることが多い.
回答ありがとうございます。
1)は確かに言われてみればそうです。
3)は明記していませんでしたが、おっしゃるとおり平均での計算量です。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- Visual Basic(VBA) 前回ご教授いただいたコードに覚えたてのループ処理で品名りんごAから順に20回for nextでループ 7 2023/01/13 22:01
- 飲食業・宿泊業・レジャー メモできないオーダーの覚え方 まず流れとして注文からレジまでの流れを大まかに説明します。わかりづらか 1 2023/02/13 00:06
- アルバイト・パート メモできないオーダーの覚え方 まず流れとして注文からレジまでの流れを大まかに説明します。わかりづらか 2 2023/02/13 00:09
- ヘアケア・ヘアアレンジ・ヘアスタイル いい感じのマッシュにならない 5 2023/02/17 11:05
- 飲食店・レストラン 飲食店で↓こういうオーダーの仕方をしたら、どうなりますか? A「拙者はライスを3つとすっ!!」 B「 3 2022/10/22 10:23
- C言語・C++・C# プログラミング c言語 4 2023/03/07 01:05
- 薬学 調剤薬局の仕組み 3 2022/07/07 15:42
- 一眼レフカメラ 金持ちが多いの? 2 2022/12/16 10:15
- 美容師・理容師 美容院のカットについて。 今日、美容院に行きました。 ロングヘアでかなり重たかったので、軽くしたい( 1 2022/05/08 23:18
- 野球 来年のWBCがとても楽しみですが、皆さんの考える侍ジャパンの最強オーダーを教えてください。 ちなみに 3 2022/12/16 10:53
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
65536は2の何乗なのでしょうか?
-
順列のプログラムについて(VB)
-
VBAの再計算が反映されない件に...
-
モジュラス103の計算とは何でし...
-
排他的論理和 BCC(水平パリテ...
-
Javaでのある数の小数点乗に...
-
ホームページビルダーで料金の...
-
Perl 初心者です。計算機能付フ...
-
エクセル 再計算とVBA の...
-
60進数の四則計算
-
標準偏差値の求め方
-
人時生産性をExcelで計算したい
-
EXCELなどで「返す」という表現
-
剰余の計算方法
-
構文解析を利用した計算プログ...
-
Date型の範囲を超える数値について
-
matlab計算での進捗状況を知りたい
-
高速化のテクニック
-
サインカーブを計算したい
-
バッチファイルでウインドウを...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
65536は2の何乗なのでしょうか?
-
VBAの再計算が反映されない件に...
-
排他的論理和 BCC(水平パリテ...
-
モジュラス103の計算とは何でし...
-
EXCELなどで「返す」という表現
-
バッチファイルでウインドウを...
-
VBAでの勤務時間計算
-
数値計算の高速化 (cos, sin, exp)
-
C# 計算処理中に実行中ウィン...
-
変化させるセルが変化しない
-
VBとVBAの違い
-
CRC8を教えてください
-
引き放し法による除算アルゴリ...
-
傾いた四角形内の範囲の条件式
-
タクシー料金の問題です
-
C言語についてです。 再帰を使...
-
CとFORTRANの計算速度はどちら...
-
VB6で正確なミリ秒を計測したい...
-
Date型の範囲を超える数値について
-
電卓でmodの計算
おすすめ情報