きまった じゅんばんで とく

アルゴリズムは「もんだいを とく きまった じゅんばん」です。ステップを ふめば こたえが でて、じゅんばんが ちがえば けっかも ちがいます。同じ じゅんばんなら だれが やっても 同じ こたえが でます。だから コンピュータに じゅんばんを かいてあげれば、いつも 同じ ことを してくれます。

大きな もんだいは 一口では とけません。だから 同じ かたちの 小さな もんだいに わけ、どの じゅんばんで とくか きめ、かけらの こたえを また 合わせます。こうして「わけて - じゅんばん - 合わせる」で 大きな もんだいを あつかうことが、まさに コンピューティング しこうの はじまりです。どんなに むずかしい もんだいでも、小さく わければ 手に つかめます。

ならべかえは ばらばらな ものを 順に ならべる ことです。となりを くらべて 大きいのを うしろに おくりつづければ、列が だんだん そろいます。一あしごとに 一つずつ じぶんの ばしょを みつけるので、どんなに ばらばらでも さいごには 列が そろいます。ととのえておけば さがすのも らくです。

となりどうし 一マスずつ くらべる 並べかえは、列が 長いほど 比較が 爆発して おそくなります。もっと かしこい 道は、列を 半分に 分け、それぞれを 並べ、並んだ二つを ファスナーのように 合わせる ことです。半分に 分け続けると 一マスだけ 残りますが、一マスは もう 並んでいるのと 同じです。合わせるのは 両がわの 先頭だけ くらべれば よいので 速いです。半分に 分けるから 層は ゆっくり ふえ、各層の 費用は 列の 長さほど。だから 全体は 一マスずつより ずっと 速く 終わります。分けて 合わせる この 考えが、速い 並べかえの こつです。

さがしは ほしいものを つまみだす ことです。一つずつ 見ると おそいですが、列が そろって いれば 半分ずつ きって ずっと はやく さがせます。半分ずつ きるのは ならんで いる ときだけ つうじます。だから ならべかえと さがしは あいぼうです。一ど 列を そろえれば のちのち はやく なります。

はやさは びょうでは なく、自ら そだつ かたちで はかります。入力の ます n が 大きく なる とき、仕事が どれだけ ふえるかを 見るのです。log n は ほとんど ふえず、n は ますの ぶん ふえ、n二じょうは ばくはつします。そして しきが ふくざつでも、いちばん 大きく そだつ こう 一つだけ のこせば いいです。3n二じょう+5n+9 は ただの n二じょうです。こうして 大きな こうだけ 見る しるしが、ビッグオー(O)です。だから 大きな データでは、半分ずつ きるのが、一つずつより くらべものに ならない ほど はやいのです。

アルゴリズムは時間だけでなく、場所（メモリ）も使います。空間計算量とは、答え以外にアルゴリズムが余分に使う場所が、入力の大きさに応じてどれだけ増えるかを測ることです。時間を測るのに使ったビッグオーのレンズを、今度はそのまま場所に当てるのです。余分な場所がいつも一枠なら O(1)、入力に応じて増えるなら O(n) です。そして時間と場所は、しばしば交換されます。先に表を作って場所を多く使えば速くなり、その場で解いて場所を節約すれば遅くなります。だから良いアルゴリズムを選ぶときは、速さだけでなく場所の値段も一緒に見ます。

大きな もんだいは、半分に わって、それぞれ といて、また 合わせて せいふく します。かんじんなのは、わった 二つの かけらが たがいに かさならない ことです。かた方で した しごとを、もう かた方が やりなおさなくて いいから。これ以上 われない ほど 小さく なれば すぐ といて、といた かけらを 上へ 合わせれば、ぜんたいの こたえが でます。にぶん たんさくも マージソートも、みな この わくぐみです。かけらが かさならない ことが、この やり方の 力です。

再帰は、もんだいを とく とき 自分を もっと 小さな 入力で また 呼ぶ ときかたです。8回で 大きな もんだいを 半分に わって せいふく しましたね。その わる ことが まさに 自分を また 呼ぶ ことです。だから 分割統治と 再帰は 一つの ものです。ほんとうに ひつようなのは 止まる ゆかです。ゆかが なければ かぎりなく 下ります。呼び出しが 一つずつ つもり、ゆかに つくと ぎゃくに 上って、こたえが 一つに 合わさります。自分を 呼ぶ、止まる ゆか、つもって 解ける。この 三つが 再帰です。

さいきは よく 同じ 小さな もんだいを 何ども ときなおします。フィボナッチの 木を 見るだけでも fib(2)が あちこちに また でてきます。といた こたえを メモに かいて また つかえば、同じものを 二ど とく ことが ありません。これが メモか です。ぎゃくに、いちばん下の 小さな 値から 表を うめて 上へ いっても 同じ かんがえです。すると しすうてきに おそかったものが せんけいに、ぐっと はやく なります。ぶんかつ とうちは わった かけらが かさならないので かいておく ものが ありませんでしたが、かさなる ときは かいておく 一手が すべてを 変えます。

どんよく アルゴリズムは、まいかい「いま いちばん よさそうな もの」を えらぶ ほうほうです。ぜんたいを 見ずに 一歩ずつ えらぶので、はやくて かんたんです。おつりを 大きい コインから わたしたり、はやく おわる かいぎから とったり するように、ある もんだいでは これが ほんとうの せいかいです。でも コインの しゅるいが へんだったり みちが こんがらがっていると、目の前の さいぜんが ぜんたいの さいぜんでは なく、わなに なる ことも あります。だから どんよくは はやくて よく あたりますが、いつも あたるわけでは ありません。

ある ときかたは サイコロを ふって なにを するかを むさくいに えらびます。クイック ソートで いつも さいごの あたいを きじゅんに すると わるい にゅうりょくで おそく なりますが、きじゅんを むさくいに えらべば その わなを さけて へいきんてきに はやく なります。また せいほうけいの 中に てんを たくさん うって、円の 中に はいった わりあいを 見れば ひろさを あらためる ことが できます。たくさん なげるほど あらためが せいかくに なります。むさくいな ときかたは まいかい おなじ こたえを やくそく できませんが、その かわり はやくて かんたんです。かくじつさを すこし わたして はやさを えるのです。

グラフは「点(たいしょう)と 線(かんけい)で えがいた え」です。点は なんにでも なれて、線は ふたつの あいだの かんけいです。ちかてつ、ともだちもう、ウェブは みんな グラフです。ツリーは そのなかで わ(じゅんかん)が ない とくべつな ばあいです。だから ツリーも グラフの ひとつです。せかいを 点と 線で 見ると、ふくざつに 見えたものが ひとめで わかります。

一つの 点から はじめて グラフ ぜんぶを まわる 二つの あるきかたが あります。はば ゆうせんは ちかい ところから 一まいずつ 波のように ひろがります。ふかさ ゆうせんは 一つの みちを さいごまで たどり、いきどまりで もどります。どちらも すべての 点を のこさず ふみますが、じゅんばんが ちがいます。そして 線に きょりの ちがいが ない とき、はば ゆうせんが ふむ じゅんばんが そのまま さいたん きょりです。

せんごとに きょりが ちがうと、わかれみちが 少ない みちが いちばん はやい わけでは ありません。だから ちかい じゅんに かぞえる だけでは だめです。スタートから ちかい てんから きょりを 一つずつ かくていし、かくていした はんいの きょうかいを 一てんずつ そとへ ひろげます。まいかい まだ かくていしていない てんの うち いちばん ちかいものを えらぶ、めの まえの さいぜんです。きょうかいが ぜんぶ ひろがれば、すべての てんまでの いちばん はやい きょりが わかります。

ある もんだいは 入力が すこし 大きく なるだけで しらべる ばあいの かずが ばくはつするので、はやい とき方が まだ 知られていません。ぜんぶの まちを 一かいずつ まわる いちばん みじかい みちを さがす セールスマンのような ものです。でも こういう もんだいは こたえを 見つけるのは むずかしくても、だれかの こたえを かくにんするのは かんたんな ことが おおいです。なら かくにんが はやい もんだいは とくのも はやい? これを P たい NP もんだいと よびますが、まだ だれも こたえを 知りません。とけていない 大きな なぞです。

かんぺきな こたえを はやく とれない むずかしい もんだいでも、「じゅうぶん よい こたえ」なら はやく とれる ことが おおいです。ある ほうほうは もう一歩 すすんで、その こたえが「さいてきの なん パーセント いない」だと ほしょうまで くれます。せいかくさを すこし わたして じかんを える、とりひきです。じかんを もっと つかえば もっと せいかくに、すくなく つかえば あまり せいかくでなく。どこで とめるかは わたしたちが えらびます。これが この りょういき ぜんたいの しめくくりです。すべての もんだいを かんぺきに とくことは できませんが、はやい ほうほうで、かしこい せんりゃくで、げんかいを 知って かしこく とりひきすれば、むずかしい もんだいの まえでも つかえる こたえを 手に できます。