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

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

ただいまの
回答率

90.48%

  • アルゴリズム

    420questions

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

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

解決済

回答 5

投稿

  • 評価
  • クリップ 4
  • VIEW 1,924

vc3000

score 180

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

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

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

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 5

checkベストアンサー

+2

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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

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

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

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/04/05 13:27

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

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

    キャンセル

0

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

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

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

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




投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

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無限大という(つまりオーダーが同じという意味)」と書かれています。

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

関連した質問

同じタグがついた質問を見る

  • アルゴリズム

    420questions

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