質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.06%

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

解決済

回答 8

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 1,512

score 162

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

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

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

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

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

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

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

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

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

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

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

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

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


[追記]

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

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

探索のアルゴリズム

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

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

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • 退会済みユーザー

    2019/03/31 02:36

    複数のユーザーから「やってほしいことだけを記載した丸投げの質問」という意見がありました
    「質問を編集する」ボタンから編集を行い、調査したこと・試したことを記入していただくと、回答が得られやすくなります。

回答 8

+2

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

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

+2

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

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

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

+1

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

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

メリット・デメリット
これらを教えて頂けばと思っております。

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

+1

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

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

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

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

+1

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

checkベストアンサー

0

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

ユークリッド互除法

ユークリッド互除法に関してはさらに発展させた拡張ユークリッド互除法が存在します.
これによって一次不定方程式の解を求めることができます

素数

色んな情報を守る「RSA暗号」というものがあります
RSA暗号とは、桁数が大きい合成数の素因数分解問題が困難であることを安全性の根拠とした公開鍵暗号の一つです。素因数分解が「鍵」なので素数が必要不可欠です.

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

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

バブルソートは直感的に理解しやすいのでコードに落とし込むのが比較的簡単になると思います.
しかし処理する時間がデータの量の2倍に比例するのに注意する必要があります.

クイックソートは名前の通り処理速度が速いことで有名です.
クイックソートをする際にデータ内の中央値を基準にするのが望ましいですが
データ量が膨大な時,基準値を探すのに時間をかけると本末転倒なのでランダムに選んだ3つのデータの
中央値を基準にするのが一般的と言われています.

そのほか もっと知りたい場合は自分で調べてみてください.

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/04/04 18:29

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

    キャンセル

  • 2019/04/04 20:16

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

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.06%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る