整列の比較回数を表す数式でよく見るO(n log n)のOって何ですか

質問

タイトルどおりなのですが、数式の(n log n)とO(n log n)では何がちがうのですか。
どなたか教えてください。

回答No.5

はなおか じった（@Jitta） · ベストアンサー

とりあえず、O()が計算量の増え方を表すための記号である、というところはOkなのでしょうか？

>それは1/2が微量だということです

　「微量」という書き方がまずかったですね。「定数」です。データ量に依存しないので、無視します。と、本にも書いてあると思います。

　計算量がどれくらいの勢いで増えていくかというのを見るためのものなので、実質的には

・O(1)　…　ハッシュなど　データ数によらずに常に一定
・O(n^2)　…　バブルソートなど　データ数により急激に増える
・O(nLog(n))　…　クイックソートなど　データ数による増え方が緩やか
・O(n)　…　リストへの挿入など　データ数による増え方が単純にデータ数に依存

くらいしか、使いません。ここで、「1」や「n^2」などより、「データ数によらずに常に一定」や「データ数により急激に増える」の方が重要なのです。いわば、この言葉を表すための便宜上の記号といってもいいかもしれません。

　n^2も、n(n-1)/2も、結局nとn（に近い値）を掛け合わせているので、右肩上がり、しかも急激に増えていきます。この「急激に増える」というのが知りたい／示したいのです。確かに計算そのものの回数は半分ですが、この「O()」が表したいのは、１億回処理するか、５千万回処理するか、ではなく、
『データ量が増えたときに処理する回数がどのような増え方をするか』
ということです。エクセルでグラフを描いてみると、よくわかると思います。「増え方」を見るので、実際の計算回数が半分だろうが百万回少なかろうが、関係ないのです。くれぐれも、「何回増えたか」ではないですよ。

「回数」ではなく、「増え方」を見るのです。と、他の方も書かれているのですが、それが理解できませんか？そのことを説明するための文にたいしてつっこんでいますけど。
#2: 「回数がどのように変化するかを大まかにみる指標」
#3: 「計算負荷の増え方を示す事ができるOという擬似関数」
　　「「増え方の度合い」とでも言う」
#4: 「計算の回数の“増え方”を表現するもの」

つまり、(n log n)は、nが決まったときの特定の数値（もしくは計算の方法）を表し、O(n log n)は、「データ数による計算回数の増え方が緩やか」であることを表します。

お礼

ご返信ありがとうございます。
なるほど、そういう意味だったのですね。
O()は増え方を表していたのですね。
私はよく、ささいなことが気になり何日も悩む傾向にありますが
この問題も「バブルソートは急激に処理が増えるんだな」程度で軽く流し、さっさと次のページへ進んでしまえば良かったですね。
関係ないですが今読んでる参考書は以前読んだとても分かりやすい参考書と同じ出版社の物なのですが、これがクソみたいに分かりにくくミスプリも、いたるところに発見します。
今後は出版社で本を選ぶのはやめようと思いました。

追伸:「「回数」ではなく、「増え方」を見るのです。と、他の方も書かれているのですが、それが理解できませんか？」
→悪かったですね理解力がなくて。
でもバカをバカにしてはいけませんよ。
バカはバカなりに一生懸命考えているのですからｗ

回答No.6

はなおか じった（@Jitta）

>→悪かったですね理解力がなくて。

　バカにしたわけではありませんが、そのようなとらえられ方をするような書き方であったなら謝ります。申し訳ありませんでした。

#2『要はOというのは飾りみたいなもので特に省略しても式の意味は変わらないということでしょうか。』
　『(n^2)の頭にOが付くことによって式の値が変わるのでは』
#3『よってO(n log n)がよく分からない場合はOを省いて(n log n)だと思えばいいですね。』
#4『n(n-1)/2がO(n^2)なので、これのOを省くとn(n-1)/2≠(n^2)となり、おお確かに全く違いますね。』

これらのことより、『どこまで理解ができているのか確かめたかった』のです。それによって書き方、説明のポイントを変えなければならないですから。

>この問題も「バブルソートは急激に処理が増えるんだな」程度で軽く流し
　いえ、疑問を持つことは大切なことです。疑問を感じなければ、学ぶことはありません。また、こうして疑問を投げていただくことにより、わかっている人も理解を進めることが出来、また『どこがわからないか』を知ることができます。このことは、教師になろうという人にはもちろん、企業でも新人教育などにとても有効なことです。

>また「10の時は100、100の時は10000。どちらにしても、同じ「100倍」」とありますが
>10000は100の100倍ですが100は10の10倍だと思うのですが、これは単なるタイプミスですか。

１．nが例えば10の時は「10*(10-1)/2=45」ですが、nが100になれば4500になります。
２．n^2で計算すると、10の時は10^10=100、100の時は100^100=10000。

(n^2)とn(n-1)/2のどちらにしても、nが10倍しか増えていないのに対して、回数は100倍に増えています。

お礼

再返信ありがとうございます。
まあ確かに阿呆な奴に、ものを教えるのは骨の折れることで相手がどのくらい理解しているかを確かめようとすれば必然的にバカにしたような発言になってしまうのでしょうね。
僕の周りには僕よりもさらに阿呆な奴がいて、そいつらに何か教えるときは「そんなことも分からないのか」というような口振りで相手を小馬鹿にしながら教えています。
だから実は僕も人のこと言える立場じゃないのでしたｗ

疑問を持つことは大切なことです、とのことですので今後も本サイトにお世話になりたいと思います。
些細な疑問もビシバシ投げつけていきますので、受け止めてください。

最後の10倍100倍の箇所はミスタイプでもなんでもなく、ただ私が受け取り間違えただけだったのですね。
増え方は、どちらの式でもいっしょということですね。

あ、こっちは本当にミスタイプ発見かも
「n*(n-1)/2」でnが100になれば4500→4950ｗ

回答No.4

はなおか じった（@Jitta）

こんにちは。

>Oが付くと、ぴったりとその値になるとは言い切れないが、
>だいたいそのくらいの値になるといったようなかんじでしょうか。
>数学の記号でいえば≒のようなかんじですね。
>よってO(n log n)がよく分からない場合はOを省いて(n log n)だと思えばいいですね。

　(n log n)は数式で、O(n log n)は「O」という関数です。高校くらいで「f()」ってやりませんでした？これはfunctionのfですが、これと同じ表記です。

　計算量を求める関数をO（OrderのOです）と定義し、その関数の値を求める計算式を「n log n」と定義します。したがって、Oを省くと「関数」が「数式」となり、全く意味が変わります。

　計算の回数の“増え方”を表現するものなので、定数的な部分は省略…というか、考えません。「n(n-1)/2」の場合、回数が増えれば1/2も微量なので省き、当然-1も微量なので省きます。
　バブルソートの回数は、nが例えば10の時は「10*(10-1)/2=45」ですが、nが100になれば4500になります。nが10倍になっているのに対し、計算回数は100倍になっています。n^2で計算すると、10の時は100、100の時は10000。どちらにしても、同じ「100倍」ですよね。この「100倍」というのを知るため（「求める」ではない）の関数です。

　数式はnがある一定の値、つまり「点」を見ますが、Order関数はnが連続する「線」を見ます。

お礼

ご返信ありがとうございます。
うーん、なんか更に泥沼にはまってしまったような感じです(汗)。
f()については多分、高校でやったのだと思いますが忘れちゃいました。
というより数学の時間は、たいてい夢を見ていましたので(汗)。
Oを省くと全く意味が変わってしまうのですか。
n(n-1)/2がO(n^2)なので、これのOを省くとn(n-1)/2≠(n^2)となり、おお確かに全く違いますね。
しかし、やっぱり良く分からん。
あと、もう1つ解答文中に疑問の残る箇所があります。
それは1/2が微量だということです。
1万円札と5千円札の違いは私にはとても微量とは思えないのですがコンピュータの世界では微量ということでしょうか。
しかしコンピュータでも5000万の処理をするのと1億の処理をするのとでは、けっこう差が出ると思うのですが、そういう問題ではないのでしょうか。
また「10の時は100、100の時は10000。どちらにしても、同じ「100倍」」とありますが
10000は100の100倍ですが100は10の10倍だと思うのですが、これは単なるタイプミスですか。
以上のことについて、よろしければ、お暇なときに再度ご回答いただけませんか。
ところで私は一応、普通科の高校を卒業しましたが高校生ほどの学力、というか理解力がありません。
ですので、ご解答の際には小中学生でも理解できるような簡単な文章をいただけると大変助かります。
お手数をおかけしてスミマセン。

回答No.3

stosh

O(n log n)っていうのは、データ量nの増減に合わせて、
(n log n) の形で計算量が増えていくような計算方式の事を言っています。
つまり、n log n の計算効率を、O(n log n)という表現で表わしているだけですね。計算負荷がわかるわけではないのですが、計算負荷の増え方を示す事ができるOという擬似関数を用意するとして、その計算方法が、n log n ですよ、というような感覚でしょうか？

orderは、整頓という意味ではなく、数学で使う表現の、「xx次」という意味です。日本語でいうなら、「増え方の度合い」とでも言うのでしょうか？ O(n^2)なら、データ量が100倍に鳴るたびに、計算量は100^2=10000で10000倍に膨れあがる、つまり大規模処理に向いていない、という事を示しています。（O(n)なら100倍、O(n log n)なら664倍）

参考URL：

http://210.150.25.33/cache?uri=http%3A%2F%2Fwww.cs.u-gakugei.ac.jp%2F%7Emiyadera%2FLECTURE%2FSortAnim%2FExAlgorithm.html

お礼

ご返信ありがとうございます。
Oが付くと、ぴったりとその値になるとは言い切れないが、だいたいそのくらいの値になるといったようなかんじでしょうか。
数学の記号でいえば≒のようなかんじですね。
よってO(n log n)がよく分からない場合はOを省いて(n log n)だと思えばいいですね。

回答No.2

gatyan

＃１の補足？

オーダー　必要な処理（ソートなら比較・入れ替え）の回数がどのように変化するかを大まかにみる指標のはず。

確か、バブルソートは O(n^2) でしたっけ？　つまり、データ数 n が増えると、n^2 のように急激に必要な処理回数が上がります。
効率のよい シェルソートなどは O(n log n) で、データ数 n が大きくなっても n log n は n^2 のように急激には増えないので、処理回数が少なくて済む（＝効率がいい）ことになります。

お礼

ご返信ありがとうございます。
うーん、未だに良く分かりません(汗。
要はOというのは飾りみたいなもので特に省略しても式の意味は変わらないということでしょうか。
しかし今私が読んでる参考書によると例えばバブルソートの比較回数はn(n-1)/2・・・・O(n^2)となっているのですがn(n-1)/2と(n^2)では倍以上の差があるので(n^2)の頭にOが付くことによって式の値が変わるのではと思ったのです。

回答No.1

asuca

O(...) という記号は order をあらわす記号です。

お礼

ご返信ありがとうございます。
orderとは整頓という意味ですか。
頭にOが付くとどうなるのですか。
ひょっとしてOが付こうが付くまいが式の意味は変わらないということでしょうか。