計算量オーダーについて O(1/n)オーダー？

質問

こんにちは、c#初心者です。

　今回は計算量オーダーの話なので、基本的に言語は関係ないと思います。

　計算量オーダーの基本的な部分は分かるのですが、O(1/n)オーダーのアルゴリズムは（今のところは）まだ見かけないというか、名前程度しか知らないので、これに関しては無知です。そこで、この場合はどういうオーダーになっているのかという質問です。
　質問は３つあります。

１）この一連の処理はO(1/n)オーダーになっているか？
int count = 1000 / length; // lengthは正の整数
for ( int i = 0; i < count; i++ ) Do(); // O(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)オーダーの処理

３）配列型のコレクション（コレクションって、c#の呼び方だったっけ？） [c#] List<T>,[c++] Bector, [Java] ArrayList(だったっけ？)のようなクラスのAddメソッドのオーダーは？

//Addメソッドの中身
if ( Capacity == Count ) Expand(); // Expandは配列の容量を２倍に拡張するO(n)処理とします。
array[Count++] = item;

　以上です。

　補足で、２）については大学の教授に「一回でもO(n^2)の処理が呼び出されたら、O(n^2)オーダーになる」と言われましたが、納得いかないです。確かに、O(1/n)オーダーの処理の後にO(n^2)オーダーの処理を行えば、そうなるのは納得いくのですが……という感じです。教授が読み間違えたとは考えにくいですが（確かにちょっと忙しそうでしたが）、念のため質問です。
　それと、３）はよくある配列型のコレクションのまねです。「もし内容物が容量一杯になれば拡張→追加」を繰り返すとした場合です。ExpandメソッドのオーダーがO(n)なので、単純に計算すればO(n)オーダーになるのですが、呼び出される頻度が「(拡張された容量)回に１回」です。
　例えば、容量が４ずつ拡張されるとすれば、「４回に１回」拡張が必要になり、１０ずつ拡張されるとすれば、「１０回に１回」の拡張が必要です。この場合、どう考えても全体として定数で割っているだけなので、O(n)オーダーのままになるのは明白なのですが、今回は容量２倍とさせていただきました。すると拡張の頻度は「（さっきまでの容量）回に１回」の頻度で、容量に反比例し、直感的にはO(Count / Capacity) = O(1)オーダーに見えるのですが、この判断は正しいでしょうか？

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

回答No.6

Tacosan · ベストアンサー

えぇっと....

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

お礼

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

補足

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

回答No.5

Tacosan

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

オーダーの定義はちょっと違うのできちんと確認しておくこと.

お礼

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

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

回答No.4

Tacosan

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)になると思っていました。

　１つ抜けていましたが、x, yは少なくとも負でない実数で、の変域は一緒です。まあ、分布が異なれば意味が無いような気もしますが。

補足

↓のL10～12の補足です。

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

回答No.3

Tacosan

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

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

お礼

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

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

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

回答No.2

Yune-Kichi

(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→∞での小さくない方の式

お礼

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

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

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

回答No.1

Tacosan

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

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

お礼

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

　１）は確かに言われてみればそうです。

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