アルゴリズムの計算量

質問

アルゴリズムの計算量とはどういう意味なんでしょうか？またそれを知るとどんな意義がありますか？
教えてください。

回答No.7

a-saitoh

>１．最悪な場合に, 少なくともこれだけはかかる
を、あまり「下限」とか「下界」とかは言わないと思いますが。。。

たとえば、「クイックソートは平均　O(n logn)だが、最悪O(n^2)のアルゴリズムだ」という言い方をします。
あるいは「クイックソートの最大計算量はO(n^2)」とか。

回答No.6

noname#26650

自分の回答No.5に補足します。
コンピュータの性能向上を待つ、というまどろっこしいことをしなくても、
現実に存在するもっと速いマシンに計算させる、という手は
もちろんあります。

パソコンレベルではなかなか歯が立たないような計算でも、
スーパーコンピュータで行なうと瞬時に解が求まる、というような話です。

回答No.5

noname#26650

>それを知るとどんな意義がありますか？

その問題をコンピュータで解くためにかかると想定される時間が
現実的な範囲に収まるかどうかが、ある程度わかると思います。

時間をかければ必ず解ける問題であることがわかっていても、
そのために百年も千年もプログラムを動かし続ける必要がありそうだ、
というのは現実的ではないですよね。そういう場合は、別のアプローチ
（画期的なアルゴリズムを開発する、コンピュータの性能向上を待つ、など）を
考えねばならなくなる、というわけです。

回答No.4

Tacosan

普通そういう文脈では「下限」じゃなくて「下界」ではないかなぁ?
ともあれ, その意味だと「計算量の解析がどれだけタイト (辛い) か」ということの指標に使えます. つまり, 「最悪の場合の計算量が O(n^3)」といわれても, これだけでは「限界を狙ってこの結果が出た」のか「甘めにみてこの結果が出た」のかが区別できません. で, 「下界が Ω(n^3)」ということであれば上下界が一致するので「これ以上解析を厳密にすることは無意味」と評価できるし, 「下界が Ω(n^2)」なら「もっと厳しく評価できるかもしれない」と考えられます.
もっとも, 下界を求めるならともかく下限を求めるのは大変なんですけど.

回答No.3

Tacosan

ちょっと確認したいんだけど, ここでの「計算量の下限」ってのは
１．最悪な場合に, 少なくともこれだけはかかる
２．最良の場合に, 少なくともこれだけはかかる
のどちら? 前者なら意味はあるけど, 後者だとしたらほとんど無意味だと思う.

補足

前者でお願いします。

回答No.2

a-saitoh

問題の計算量の下限は意味があるけど、アルゴリズムの計算量の下限はなにか有意義ななにかがあったかなぁ？？

回答No.1

Tacosan

計算量ってのは, アルゴリズムを実行するときに「どのくらいの資源 (時間やメモリ) を使うか」の指標.

補足

言葉足らずですいません。
計算量の下限について知りたいです。