計算量のO(n)記法について

Question

https://ja.wikipedia.org/wiki/%E3%83%A9%E3%83%B3%E3%83%80%E3%82%A6%E3%81%AE%E8%A8%98%E5%8F%B7
上記記事の「厳密な定義」によると、
「f(x) が x → ∞ のとき O(g(x)) 程度である」
とは、xが十分大きいとき、fの絶対値がgの絶対値の定数倍で抑えられるということのようです。

そうだとすると、例えばO(n*log n)のアルゴリズムはすべてO(n^2)でもあるといっても定義上間違いではないですよね？
しかし実際には「クイックソートの平均計算量はO(n^2)である」と言えば間違い扱いされると思います。
計算機科学の世界では厳密にはどういうことになっているのでしょうか？

Answer 1

Θ-記法やΩ-記法はご存じでしょうか？
O-記法が上限を表すイメージで、Ω-記法が下限を表し、
Θ-記法はその両方を表すイメージです。

vc3000さんが参照しているWikipediaのページにも説明がありますし、
計算量 - Security Akademeia
オーダー記法・その4 - あざらしとペンギンの問題
等にも記述があります。

実際に、O(n*log n)と言った場合に、本当はΘ(n * log n)を意味していることが
多いように思います。

Wikipediaのページにも、以下の様な記述があります。

もっと正確に漸近的に漸近的 tight bound であることを明示するならば Θ-記法を用いる。

以下の質問の回答にも、
What is the difference between Θ(n) and O(n)?

when people talk about O(g(n)) they actually mean Θ(g(n)) but technically, there is a difference.

とあります。

Answer 2

これはO(n)記法の定義についてというよりは極限の定義についての質問になると思います。そして、これはとても重要な疑問です。

極限の話をしてしまいますが、y=1/xという関数、普通なら「xを大きくしていくときyは0に限りなく近づいていく。0がこの関数の極限である」と言います。
ところが、xを大きくしていくとき、y=-1にだって限りなく近づいていっています。-1を極限と呼んでもいいはず。なぜそう呼ばないのか？

ご質問はこの極限の疑問とまったく同じことです。高校までの数学ではこの疑問には答えられませんでしたね。なぜなら極限の厳密な定義をしていなかったからです。大学だと厳密に定義しました。ε-δ論法により、-1は極限となりません。

クイックソートの平均時間をO(n^2)と表現できないのも同様の理路だと思っていただけると。

Comments

[swordone]

>ところが、xを大きくしていくとき、y=-1にだって限りなく近づいていっています。

限りなくは近づかないよね。1以上の差はあるわけだから。

Answer 3

東大出版の解析入門I（杉浦著）という、数学の十分に枯れた（誤植が少なく、評価の定まった）本があります。そこではランダウの記号は「lim_n->∞(f(n)/g(n))=0の時、f(n)はο(g)である」、「lim_n->∞(f(n)/g(n))=定数の時、f(n)はΟ(g)である」として定義されています（本当はもうちょっと厳密に書いてありますが）。また、「lim_n->∞(f(n)/g(n))=c(≠0)のとき、f~cgと書き、fとgは同次の無限小or無限大という（つまりオーダーが同じという意味）」と書かれています。

もちろん、Ο(nlog(n))の関数はΟ(n^2)の関数に含まれますが、1+1は1より大きいといった程度の情報しか教えてくれません。
ですので、普通にランダウ記号を使うときは、f~cgであるという意味で、つまり、「f(n)はΟ(g)の関数である」のようにして使われます。この意味ではΟ(nlog(n))とΟ(n^2)の集合は互いにかぶりません。

ΩやΘを使った表記もあるようですが、余り流行っていない理由としては、それらの記号は他の意味で使われることが非常に多いため、オーダーを表す記号なんかにそんなにたくさんギリシャ文字を割けないよーっていうことだと思います。

Answer 4

ご覧になった記事の最初に「ランダウの記号（ランダウのきごう、英: Landau symbol）は、関数極限における漸近挙動、すなわち値の変動のおおよその評価を与えるための記法である。」と説明されています。

O(nlog n)のアルゴリズムはデータの大きさｎに対して、その計算時間がおおよそ kn+log(n) で抑えられます (kは定数）ので、漸近挙動を示していると言えます。

しかし、mnn (mは定数）はO(n*log n)のアルゴリズムの計算時間と乖離しているので、漸近挙動を示しているとは言えません。

「クイックソートの平均計算量はO(n^2)である」と言えば間違いなのは、値の変動のおおよその評価となっていないからです。

Answer 5

定義上は、確かに「O(n*log n)のアルゴリズムはすべてO(n^2)」です。O(n^2)のアルゴリズムが必要な場所にマージソートを使っても、別に問題はありません。

ただ、計算量やメモリの使用量といった資源は、必要以上に大きく使うことも可能ですので、アルゴリズム自体の性能を表現する際には小さなもので表す慣習になっています。