素数・最大公約数のアルゴリズムの使い道及び探索・整列アルゴリズムのメリット・デメリットについて

「コンピューターはなぜ動くのか？」の「第５章のアルゴリズムと仲良くなる7つのポイント」（P106）にて、主な定番アルゴリズムとして、

表5.1　主な定番アルゴリズム

①ユーグリットの互除去
②エラトステネスのふるい
③線型探索
④2分探索
⑤ハッシュ法
⑥バブル・ソート
⑦クイック・ソート

これらの上記のアルゴリズムがあり、そのアルゴリズムの用途には大きく4つに分けて

最大公約数のアルゴリズム
素数のアルゴリズム
データ探索のアルゴリズム
整列のアルゴリズム

上記の用途に分けることができますが、特に①～②の用途については何の用途に応用できると思われますか？
私からすれば、①～②は「最大公約数」と「素数」を求めることだけしか用途がないと思いますが…

さらに、③～④のアルゴリズムの用途においてのメリット・デメリットについて

3.データ探索のアルゴリズム
③線型探索
④2分探索
⑤ハッシュ法

についてのメリット・デメリット

4.整列のアルゴリズム
⑥バブル・ソート
⑦クイック・ソート

についてのメリット・デメリット

これらを教えて頂けばと思っております。

よろしくお願いたします。

[追記]

**⑥バブル・ソート
⑦クイック・ソート **

についてのメリット・デメリット は良くわかりました。しかし、

探索のアルゴリズム

③線型探索
④2分探索
⑤ハッシュ法

のそれぞれのメリット・デメリットは何なんでしょうか？よろしくお願いいたします。

行動規範の内容に同意します

回答8件

上記の用途に分けることができますが、特に①～②の用途については何の用途に応用できると思われますか？

私からすれば、①～②は「最大公約数」と「素数」を求めることだけしか用途がないと思いますが…

その通りです。そのための専用アルゴリズムなので。
「最大公約数」と「素数」が何の役に立つかは数学（算数）の問題なので、このサイト以外で質問してください。

さらに、③～④のアルゴリズムの用途においてのメリット・デメリットについて

メリット・デメリットを考える前に、それぞれのアルゴリズム自体について調べましょう。

投稿2019/03/30 17:34

otn

総合スコア84499

特に①～②の用途については何の用途に応用できると思われますか？

私からすれば、①～②は「最大公約数」と「素数」を求めることだけしか用途がないと思いますが…

maisumakunさんの回答もごもっともなのですが、数論の扱う領域が暗号に使えるとわかったのは最近(半世紀くらい)のことで、それ以前は単に数学的興味から研究されていたと思います(名前になっている人の古さからわかる通り、どちらも超古典です)。

だから駄目、というものではないです。面白いものであるとか、わかりやすいので初学者向けだとかの理由で、定番として紹介されてもいいでしょう。

投稿2019/03/30 10:39

hayataka2049

総合スコア30933

東大の先生がやさしく教える「なんで数学を勉強しなきゃいけないの？」

こういうことなのでは

投稿2019/03/31 18:01

swordone

総合スコア20651

ユークリッドの互除法とかエラトステネスのふるいは仰るとおり最大公約数計算や素数判定計算に用いられます。というか、その手段の一つに過ぎず、それ以上のものではないです。

最大公約数」と「素数」を求めることだけしか用途がない

その通りです。そう言われればそれまでです。もっとも、この結果として複雑な処理を実現していることも間違いではありません。みなさんが仰るとおり暗号はその一つです。

同様に、探索や整列も大きな処理の中の一要素に過ぎません。それ自体の価値は大きくないです。実際にエクセルを使う際に整列することや、ファイル検索することもあると思います。これは「ユーザがやりたいから」であって、この目的は千差万別です。

アルゴリズムは結局のところ、手段に過ぎません。目的はその先にあります。また、代案がない場合はそれを使うしかありません。用途とかメリット・デメリットとか言われれても即答はできません。

投稿2019/03/31 11:24

HogeAnimalLover

総合スコア4830

特に①～②の用途については何の用途に応用できると思われますか？

たとえばTeratailもHTTPSの通信ですが、暗号技術を支えているのは素数です。素数に関する高度なアルゴリズムは、現代インターネットでは当たり前に使われるインフラとなっています。

メリット・デメリット

これらを教えて頂けばと思っております。

本で扱っている以上は、それらについても触れられているかと思います。「記載がなかった」、あるいは「呼んでもわからなかった」のであれば、その旨の追記をお願いします。

投稿2019/03/30 04:41

maisumakun

総合スコア145183

探索のアルゴリズム

③線型探索
④2分探索
⑤ハッシュ法
のそれぞれのメリット・デメリットは何なんでしょうか？

それぞれの 時間計算量 と 空間計算量 やね。

投稿2019/04/01 15:05

episteme

総合スコア16614

mr0237

2019/04/04 09:29

すいません。もう少し具体的に教えてくれれば幸いです。よろしくお願いいたします。

episteme

2019/04/04 11:16

そのままですよ。たとえば時間計算量なら3,4,5はそれぞれ O(N), O(logN), O(1) ですからハッシュがいちばん速い。

行動規範の内容に同意します

上記の用途に分けることができますが、特に①～②の用途については何の用途に応用できると思われますか？

他の回答にもあるように、あまり実用的には使われてない気がします。
一つ、よく見るところを見つけました。
プログラム入門時のサンプル or 演習ブログラム。
暗号化コードなんて、理屈が分かってもすぐに書けない事が多いですが、これらは、理論もシンプルで、演習用には手頃なんでしょう。

投稿2019/03/31 12:23

pepperleaf

総合スコア6383

ベストアンサー

上記の用途に分けることができますが、特に①～②の用途については何の用途に応用できると思われますか？

私からすれば、①～②は「最大公約数」と「素数」を求めることだけしか用途がないと思いますが…

ユークリッド互除法

ユークリッド互除法に関してはさらに発展させた拡張ユークリッド互除法が存在します.
これによって一次不定方程式の解を求めることができます
###素数
色んな情報を守る「RSA暗号」というものがあります
RSA暗号とは、桁数が大きい合成数の素因数分解問題が困難であることを安全性の根拠とした公開鍵暗号の一つです。素因数分解が「鍵」なので素数が必要不可欠です.