- 締切済み
アルゴリズムの計算量
アルゴリズムの計算量とはどういう意味なんでしょうか？またそれを知るとどんな意義がありますか？ 教えてください。
- ilias
- お礼率19% (4/21)
- その他（プログラミング・開発）
- 回答数7
- ありがとう数3
- みんなの回答 （7）
- 専門家の回答
みんなの回答
- a-saitoh
- ベストアンサー率30% (524/1722)
>１．最悪な場合に, 少なくともこれだけはかかる を、あまり「下限」とか「下界」とかは言わないと思いますが。。。 たとえば、「クイックソートは平均 O(n logn)だが、最悪O(n^2)のアルゴリズムだ」という言い方をします。 あるいは「クイックソートの最大計算量はO(n^2)」とか。
自分の回答No.5に補足します。 コンピュータの性能向上を待つ、というまどろっこしいことをしなくても、 現実に存在するもっと速いマシンに計算させる、という手は もちろんあります。 パソコンレベルではなかなか歯が立たないような計算でも、 スーパーコンピュータで行なうと瞬時に解が求まる、というような話です。
>それを知るとどんな意義がありますか？ その問題をコンピュータで解くためにかかると想定される時間が 現実的な範囲に収まるかどうかが、ある程度わかると思います。 時間をかければ必ず解ける問題であることがわかっていても、 そのために百年も千年もプログラムを動かし続ける必要がありそうだ、 というのは現実的ではないですよね。そういう場合は、別のアプローチ （画期的なアルゴリズムを開発する、コンピュータの性能向上を待つ、など）を 考えねばならなくなる、というわけです。
- Tacosan
- ベストアンサー率23% (3656/15482)
普通そういう文脈では「下限」じゃなくて「下界」ではないかなぁ? ともあれ, その意味だと「計算量の解析がどれだけタイト (辛い) か」ということの指標に使えます. つまり, 「最悪の場合の計算量が O(n^3)」といわれても, これだけでは「限界を狙ってこの結果が出た」のか「甘めにみてこの結果が出た」のかが区別できません. で, 「下界が Ω(n^3)」ということであれば上下界が一致するので「これ以上解析を厳密にすることは無意味」と評価できるし, 「下界が Ω(n^2)」なら「もっと厳しく評価できるかもしれない」と考えられます. もっとも, 下界を求めるならともかく下限を求めるのは大変なんですけど.
- Tacosan
- ベストアンサー率23% (3656/15482)
ちょっと確認したいんだけど, ここでの「計算量の下限」ってのは １．最悪な場合に, 少なくともこれだけはかかる ２．最良の場合に, 少なくともこれだけはかかる のどちら? 前者なら意味はあるけど, 後者だとしたらほとんど無意味だと思う.
- a-saitoh
- ベストアンサー率30% (524/1722)
問題の計算量の下限は意味があるけど、アルゴリズムの計算量の下限はなにか有意義ななにかがあったかなぁ？？
- Tacosan
- ベストアンサー率23% (3656/15482)
計算量ってのは, アルゴリズムを実行するときに「どのくらいの資源 (時間やメモリ) を使うか」の指標.
補足
言葉足らずですいません。 計算量の下限について知りたいです。
関連するQ&A
- 2進アルゴリズムの時間計算量
ベキ乗計算を2進アルゴリズムで解いた場合の時間計算量を求める方法を教えてください。 x^nの時の時間計算量でn=2,3以外の時でn=2p,2p+1の時で場合わけして(pは整数)数学的帰納法で解いてあるのは見た事はあるのですが、どこからその仮定を持ってきたのか見当がつきません。 どうかお願いします。 n>3のときの時間計算量kは k<=(2*log(n))-1 となっていました。
- ベストアンサー
- その他（プログラミング・開発）
- アルゴリズム
アルゴリズムの勉強をしていて、時間計算量に関する問題があり、解いたのですが、解答が載ってなく困ってます。正誤の判断と、もし間違っているなら、何が間違っているのかを教えて頂けると助かります。 ある問題において、大きさ(データ量)nに対して、アルゴリズムA、B、Cの時間計算量が、それぞれn、n^2(nの2乗)、2^n(2のn乗)であるとする。 (1)アルゴリズムAを用いて10秒間にn=100の問題が解けた。20秒かけるとき扱える問題の大きさnの値を求めよ。 解) n=100*2 =200 (2)ある計算機を用いてアルゴリズムBで10秒間にn=100の問題が解けた。100倍早い計算機を用いたとき、10秒間に扱える問題の大きさを求めよ。 解) 求める問題の大きさをxとおくと n=(100^2)*100 =10000*100 =1000000 (3)アルゴリズムCを用いて1時間にn=20の問題が解けた。n=40の問題を解くのに何時間かかるか。 解) 2^40=(2^20)*(2^20) =1*(2^20) =2^20[時間]
- ベストアンサー
- その他（プログラミング・開発）
- 決定木を用いて、ソーティングアルゴリズムの計算量の限界を説明するにはど
決定木を用いて、ソーティングアルゴリズムの計算量の限界を説明するにはどうすればいいですか？ 教えてください。
- ベストアンサー
- その他（プログラミング・開発）
- ハミルトン閉路の計算量についての質問です。
ハミルトン閉路の計算量についての質問です。 教科書で、ハミルトン閉路の計算量が２のｎ乗となっていたのですが、 なぜ、その計算量なのか、ということがよくわかりません。 自分的には、ハミルトン閉路の最良アルゴリズムが、全数検索アルゴリズムであるので、 節点の順列すべてに対してハミルトン閉路か否かを調べる必要があるから、というような 理由を考えたのですが、 具体的になぜ２のｎ乗なのかがいまいちわかりません。 分かる方おられましたらお教え下さい。 お願いし致します。
- ベストアンサー
- 数学・算数
- アルゴリズムとは何なのでしょうか？
学校でアルゴリズムを習っているのですが、 アルゴリズムとは何なのでしょうか？ 教科書として、 「新・明解 C言語によるアルゴリズムとデータ構造」という本を買ったのですが、 内容的には以前C言語を勉強するために読んだC言語の勉強本とあまり変わらないような気がします。 スタックやキュー、ソートに検索など確かにC言語を教わる本には書いてないことはありましたが、 要するにC言語の別の面ということだと思いました。 意味的にはアルゴリズムは数学でいう計算方法、 つまり答えを求めるための色々な方法というように考えたのですが、 実際アルゴリズムとはどのようなものと理解すればいいのでしょうか？
- ベストアンサー
- C・C++・C#
- 素数判定アルゴリズム内の剰余計算
今勉強している任意倍長精度整数の素数を判定するアルゴリズム内で x^q mod n という計算をするところがあるのですが、 正確に計算しようとすると計算量が膨れ上がってしまって 高速にできなくて困っています。 参考にしている文献に "x^q mod nの計算ではx^q mod nを正確に求める必要は無く、 x^q ≡ x^q' (mod n)となる x^q'でよい"という記述があるのですが どういう意味なのかよくわかりません。 どなたか教えていただけないでしょうか？
- 締切済み
- その他（プログラミング・開発）
- アルゴリズムって・・・・
CAMのアルゴリズムで・・・・ と聞く事が多々あるのですが、アルゴリズムで計算？ するってどう言う事でしょうか？ 情けない質問でスミマセンが誰か教えて下さい！！
- 締切済み
- CAM
- 線量の計算アルゴリズムの乗っているサイトや本
計算アルゴリズムのAAA,PBC,Acuros XB法について詳しく乗っている本やサイトをしりませんか？できれば、アルゴリズムの進化なども載っていると嬉しいです
- 締切済み
- 情報工学
- アルゴリズムについて
「手作業によるソート」がレポートの課題として出されました。 「手作業のために効率的なアルゴリズムを考えて提案して分析しなさい」 条件は次の通り: 資料がそれぞれ A4 の紙一枚。見やすい位置に10桁の番号が書かれている。その番号の昇順にソートする。番号の分布については一切不明。二つのケースを想定: 1) 一人で資料5000枚をソート; 2) 20人で資料50000枚をソート。二つのケースに使えるアルゴリズム一つ、又は両ケースに使えるアルゴリズム一つでもよい。分析では O() での計算量 (理由つき) と実際に想定される時間。今まで習ったアルゴリズムとの類似点や相違点、手作業の特徴に考量した点などについても論じる。 何をすれば良いのかが分かりません。少しでも作業の道筋を示していただければ幸いです。 よろしくお願いします。
- ベストアンサー
- その他（学問・教育）
補足
前者でお願いします。