忍者ブログ

「アルゴリズム」というのは、簡単に言ってしまえば、「何かをする手順」のこと。

そして、何かをするにしても、色々なやり方があり、どのやり方にも一長一短があり、もっと端的に、ある見方をすれば、あるやり方は他のやり方よりも優れている(ダメだ)という判断が下せる(こともある)。

アルゴリズムに関して、こうした優劣の判断は、大きく分けて「空間的効率」と「時間的効率」という2つの側面から為され、その中でも時間的効率ということを主に問題にすることが多い。というのも、アルゴリズムの優劣によって、同じ問題を特にしても、「劇的」と言ってもいいような差が出るからだ。

たとえば、今ここに1秒間につき1億回の演算が可能なプロセッサがあるとしよう。そして、何かあることを為そうというときの要素数nに応じて、n、n2、そして2nの処理数を要する3つのアルゴリズムがあるとする。このとき、処理にかける要素数によって、各アルゴリズムがその仕事を為し果せる時間は、以下のようになる。

n n2 2n
n=10 10-7 10-6 10-5
n=100 10-6 10-4 4×1014



要素数nが10だと、どのアルゴリズムもマイクロ秒のオーダで処理が終わり、何てことはない。問題は、処理する要素数が増えるにしたがって、どれぐらい処理に要する時間が増えるか、ということで、nが100のときを見てもらうと……要素数nに対して処理がn秒とn2秒かかるアルゴリズムに関しては、まだマイクロ秒のうちに処理が終わるけど、処理に2n秒要するアルゴリズムは、な、何と、マイクロ秒どころか、単位からして「」になっちゃってる。しかも、4×1014っつーんだから、これ、40兆年ですよ、40兆年

斯様に、処理する要素数nが肩に乗っかった形で処理時間が表されるアルゴリズムは、「指数時間を要する」と言って、まあ、確かに、処理する要素数が小さい分には実用的だったり、何にせよ有限時間では処理は終わるし、端的に「解決不能」ではないんだけど……普通こういうのは「アルゴリズム」とは呼べないような代物。

で、アルゴリズムのこうした時間的効率(複雑さ)を計る指標として、O(ラージオー)記法というのとΩ(ラージオメガ)記法というのとΘ(ラージシータ)記法というのがあって、定義は以下の通り。

あるアルゴリズムの実行時間がその処理する要素数nの函数f(n)で表せ、それに対してある正の定数cとある正の定数n0が存在し、すべてのn≧n0に対してある函数g(x)が存在して、

  0≦f(n)≦O(g(n))

  0≦Ω(g(n))≦f(n)

  0≦Ω(g(n))≦f(n)≦O(g(n))

と表せる場合、「(処理にf(n)かかる)あるアルゴリズムはO(g(n))(あるいはΩ(g(n))、Θ(g(n)))のオーダである」などと言う。

たとえば、あるアルゴリズムAの時間効率がf(x)=60n2+5n+1と表せる場合、60n2+5n+1≦60n2+5n2+n2=66n2だから、c=66とg(n)=n2すれば、O(n2)と表せ、ゆえに、アルゴリズムAの時間効率はO(n2)、というわけ。

さらに、60n2≦60n2+5n+1だから、このアルゴリズムのオーダはΩ(n2)でもあり、ゆえにΘ(n2)でもある。



そんな感じで、「仕込み」は終わりとして、次回からは色んなソートアルゴリズムを見てきましょ。

PR
この記事にコメントする
お名前
メールアドレス
URL
コメント
NP完全問題に関しては「巡回セールスマン問題」っていう直観に訴えかけやすい問題があって、それをここで紹介はできないけど、チェスの世界での詰め碁?みたいな問題でも11手詰めとかになると人間離れした難易度になってくる。
なんてヨタ話と、関わりは、あんの?
宮本浩樹 2005/09/26(Mon)21:59:00 編集
確かに「巡回セールスマン問題」は、問題としては直観に訴えるかもしれないけど、それがどうして複雑なのか?ということまでは、直観的には分からない。むしろ、このエントリでのように、問題が代数的なフォーマリスムに落とし込まれていた方が、それが複雑であるかどうか、そして、複雑であるならどの程度、どういう風に複雑なのかが分かりやすい。

何にせよ、巡回セールスマン問題も、そして詰め将棋のような問題も、複雑さを云々するためにはまずこうしたフォーマリスムに変換する必要がある。

というわけで、関わりあり。
はやし 2005/09/27(Tue)05:33:00 編集
 巡回セールスマン問題ってなによ!太った黒服黒帽子の男がドーン!で大騒ぎって奴ですかね(それは藤子F)とか思ってググったら見つけました。
<a href="http
へー。
で、やってみたら、一回目で最短だせました。おお凄いぞ自分。
でも、アルゴリズムにすると…最大探索深度=点の数=nとして、探索時点深度での最短距離をsdとすると、
えーと、探索深度が深くなるほど足きり値を小さくしていけば、ほどほどの効率化はできるかなぁ、とか素人考えに思いましたが数学苦手なんで適当です。なんか変数宣言した意味がなかったですね。ではでは。
めむひ 2005/09/27(Tue)21:29:00 編集
巡回セールスマン問題、これ専門的に言い換えると、重み付きグラフでの最短ハミルトニアン経路を発見するってことなんですけど……って、そんな言い換えをしたからって、何も分かりやすくならないな。

で、この手の問題って、計算機にかけるよりも、人間が直接ヒューリスティックに解いちゃった方がいい類の問題ですね、今のところ。

というのも、たとえば巡回する都市数が30だとしても、全部の経路をチェックして比較するのに、30!(30の階乗)のステップ数を要し、1ステップを1ピコセカンド(1秒の12分の1)で実行できるにしても、何億年か(どころじゃなくて、何兆年、かも)かかっちゃうってことで……これ、いくら効率化したって、実用に耐えられる程度の効率化は難しい、ってことになっちゃう。

ってことで、この「巡回セールスマン問題」は、巡回する都市数がちっちゃいうちはまだどうにかなるけど、大きくなるともうお手上げ、ってな問題なわけです。
はやし 2005/09/28(Wed)01:46:00 編集
この記事へのトラックバック
この記事にトラックバックする:
カレンダー
02 2017/03 04
S M T W T F S
1 2 3 4
5 6 7 8 9 10 11
12 13 15 16 17 18
19 20 22 23 24
27 28 29 30 31
最新トラックバック
メール
ブログ作成者(はやし)に直接訴えたいことがある、という場合は、下のアドレスにメールをどうぞ。

thayashi#ucalgary.ca
(#を@に置換してください)

ブログ内検索
Google
WWW を検索 このブログ内を検索

はやしのブログ内で紹介された
 書籍の検索はこちら
 音盤の検索はこちら
ランダムおすすめ
(忍者ブログに引越してから、うまくうごかなくなってしまいました。いつか、直します)
Randombook
このブログで紹介したことのある本をランダム表示。
Randomusic
このブログで紹介したことのある音をランダム表示。
自分がらみのリンク
はやしのブログ書籍一覧
このブログで言及された書籍の一覧。
はやしのブログ音盤一覧
このブログで言及された音盤の一覧。
最近のおすすめ本
最近のおすすめ音

Copyright © [ はやしのブログ ]
No right reserved except those which belong to someone else.
Special Template : 忍者ブログ de テンプレート and ブログアクセスアップ
Special Thanks : 忍者ブログ
Commercial message : [PR]