質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.48%
アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

Q&A

解決済

5回答

6247閲覧

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

vc3000

総合スコア196

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

1グッド

4クリップ

投稿2015/09/15 01:25

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)である」と言えば間違い扱いされると思います。
計算機科学の世界では厳密にはどういうことになっているのでしょうか?

ikuwow👍を押しています

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答5

0

ベストアンサー

Θ-記法やΩ-記法はご存じでしょうか?
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.

とあります。

投稿2015/09/15 02:34

編集2015/09/15 03:45
eripong

総合スコア1546

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

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

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

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

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

投稿2015/09/15 01:35

yuba

総合スコア5568

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

swordone

2018/04/05 04:27

>ところが、xを大きくしていくとき、y=-1にだって限りなく近づいていっています。 限りなくは近づかないよね。1以上の差はあるわけだから。
guest

0

東大出版の解析入門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)の関数である」のようにして使われます。この意味ではΟ(n
log(n))とΟ(n^2)の集合は互いにかぶりません。

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

投稿2016/02/09 06:25

Paalon

総合スコア232

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

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

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

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

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

投稿2015/09/15 01:53

coco_bauer

総合スコア6915

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

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

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

投稿2015/09/15 01:31

maisumakun

総合スコア145184

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.48%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問