締切済み

アルゴリズムの計算量

2007/02/13 06:54

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

ilias
お礼率19% (4/21)

その他（プログラミング・開発）
回答数7
ありがとう数3

みんなの回答 （7）
専門家の回答

みんなの回答

a-saitoh
ベストアンサー率30% (524/1722)

2007/02/15 16:15 回答No.7

>１．最悪な場合に, 少なくともこれだけはかかるを、あまり「下限」とか「下界」とかは言わないと思いますが。。。たとえば、「クイックソートは平均　O(n logn)だが、最悪O(n^2)のアルゴリズムだ」という言い方をします。あるいは「クイックソートの最大計算量はO(n^2)」とか。

ログインすると、全ての回答が全文表示されます。

noname#26650

2007/02/15 13:57 回答No.6

自分の回答No.5に補足します。コンピュータの性能向上を待つ、というまどろっこしいことをしなくても、現実に存在するもっと速いマシンに計算させる、という手はもちろんあります。パソコンレベルではなかなか歯が立たないような計算でも、スーパーコンピュータで行なうと瞬時に解が求まる、というような話です。

ログインすると、全ての回答が全文表示されます。

noname#26650

2007/02/15 13:50 回答No.5

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

ログインすると、全ての回答が全文表示されます。

Tacosan
ベストアンサー率23% (3656/15482)

2007/02/15 13:35 回答No.4

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

ログインすると、全ての回答が全文表示されます。