プロが教えるわが家の防犯対策術!

 こんにちは、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)オーダーに見えるのですが、この判断は正しいでしょうか?

 皆さんのご意見を伺わせてください。

A 回答 (6件)

えぇっと....



x * y ≦O(max{x, y}^2) って書かれると, 今度は「その不等号って何?」ってなっちゃうんだよね. = を使えば問題ないのに, 逆に怪しい不等号をなんでわざわざ使っちゃうかなぁ.

この回答への補足

 ああ、書き間違いです。多分x * y = O(max{x, y})とx * y ≦ max{x, y}が単に混ざっただけかと(さすがに、分かってらっしゃったとは思うんですけれどね、文脈から)。

補足日時:2012/10/08 08:28
    • good
    • 0
この回答へのお礼

 O(xy)なんかをO(n^2)のように簡素化して、shortの列挙体で表そうと思っていましたが、諦めてlongの列挙体 使います。
 回答ありがとうございました。

お礼日時:2012/10/11 21:43

最初から「x と y の大きい方を n とする」といっておけばいいんだけどねぇ. ただ, 「x と y の大きい方を n とする」といった時点で「x, y, nは互いに独立」とは言わない.



オーダーの定義はちょっと違うのできちんと確認しておくこと.
    • good
    • 0
この回答へのお礼

 ご指摘ありがとうございます。

 そういえばそうですね。あんまりその辺は気にした事がなかったので(今思えば、いつも、こんな大雑把な思考しかしてないですね。だから、こんな質問ばかりしているのか。よく今まで来れたもんだと自分でも驚く)。
 そういえば、オーダーの定義には絶対値になっていたような。あと、x0と、cにももう少し規制があったような(少なくとも1つは存在するだったかな?)……。
 それで、本題なのですが、結局は、x * y ≦O(max{x, y}^2)にはならないってことですか?

お礼日時:2012/10/08 01:10

x や y と n が関係ないのなら, ますます


x * y = O(n^2)
などと書くことはできません. オーダーの意味, 理解してる?

この回答への補足

 ↓のL10~12の補足です。

 もちろん、xでもyでもなく、nを使っている時点でg(x)では無いのですが……。

補足日時:2012/10/07 15:20
    • good
    • 0
この回答へのお礼

 ご指摘ありがとうございます。

 理解していると言えるかどうか分かりませんが、アルゴリズムの速度の指標ですよね。どの程度の速度で計算量が成長していくかを大まかに示した。
 プリントをなくしてしまったので、細かい部分は忘れましたが、
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は少なくとも負でない実数で、の変域は一緒です。まあ、分布が異なれば意味が無いような気もしますが。

お礼日時:2012/10/07 14:47

#2 へのお礼の最後のところだけ... なんだけど....



#1 に
「n が何を意味するのか」ってところから始めないとダメ
って書いておいたんだけど, 理解できてます? x や y と n の関係, どこにも書いてないよ.
    • good
    • 0
この回答へのお礼

 ご指摘ありがとうございます。

 どの程度の理解が求められているのか分かりませんが……。とりあえず、x, y, nは互いに独立した任意の変数です(な訳で、関係書いていませんでした。ひょっとしたら、nはx, yの平均の方が良いのかもしれませんが)。

 例えば、[x, y]のサイズの2次元配列があったとして、この配列を拡張やコピーする場合です。この場合、O(x * y)オーダーになると思いますが、どちらも(x→∞), (y→∞)として考えるのであれば、他の変数nを用意して、(n→∞)で大雑把にO(n^2)とみなす事は出来るのか? という事を質問したかったわけです。

お礼日時:2012/10/07 00:10

(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→∞での小さくない方の式
    • good
    • 0
この回答へのお礼

 回答ありがとうございます。

 納得しました。ありがとうございます。
 それと、ΩにΘ、良く分からなかったので調べてみました。意味は分かったのですが、3)のような場合で、例えばさらに2次元配列(とりあえず、長方ではなく正方形とします)のクラスを想定するとAddメソッドは、Ω(1)、O(n^2)になると思いますが、実際の平均はO(n)になりますよね?
 この場合、ΩとOのどちらを見ても平均がO(n)である事にはたどり着けないので、メソッドの(何度も呼び出した場合の)平均の(ならし?)計算量も説明(概要か詳細)に加えていたほうがよいでしょうか? (特にライブラリのような場合)
 その場合、O-記法を使っても良いのでしょうか?

 と、大事なことを忘れていました。いまさらなのですが、x, yは変数として、 x * y = O(n^2)と見ることは出来るのでしょうか? それとも、O(x * y)のように記述するのでしょうか?

お礼日時:2012/10/06 11:13

1) はそもそも count を計算するために O(1) 必要では? まあ, 「n が何を意味するのか」ってところから始めないとダメだけど, ね.



3) は... まず, 「1回追加するのに O(1)」とはいえないことはいいね? もちろん「n回追加すると O(n)」だから, 「平均すると」 O(1) とはいえる. ただ, これは単純な計算量ではなく, amortized complexity (ならし計算量) とか言ったりすることが多い.
    • good
    • 0
この回答へのお礼

 回答ありがとうございます。

 1)は確かに言われてみればそうです。

 3)は明記していませんでしたが、おっしゃるとおり平均での計算量です。

お礼日時:2012/10/06 10:50

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!