テスト

よしデブ Blog

プログラミング、Web、IoTの話を発信。

【現役エンジニアが徹底解説】アルゴリズムってそもそも何よ?

はじめに

こんにちは、よしデブです。

今日のテーマは アルゴリズム です。

昨日華金した後(飲んだ後)にふらっと本屋さんに立ち寄ったんですが、ITに関する本がたくさん並んでまして、個人的にとても気に入りました。

その中で、アルゴリズムを、はじめよう』という本を見つけました。

アルゴリズムを、はじめる...?🧐 アルゴリズム計算方法って意味で"はじめられる"ものではないような...

ということで、現役エンジニアがアルゴリズムについてお話します!

アルゴリズム(Algorithm)

アルゴリズム(英: algorithm [ˈælgəˌrɪðəm])とは、数学、コンピューティング、言語学、あるいは関連する分野において、問題を解くための手順を定式化した形で表現したものを言う。算法と訳されることもある。 アルゴリズム - Wikipedia

ズバリ、アルゴリズムとは計算方法です。 ある問題に対して どのようにして解決するか、というHowを表した言葉です。

最適なアルゴリズム

ある問題を解決するためのアルゴリズムは1つとは限りませんが、最適なアルゴリズムというものは存在します。

例えば、大阪から東京までの移動方法は以下のようなものがあります。

  • 飛行機✈️
  • 新幹線🚄
  • 夜行バス🚌

これらのうち、一番早く移動したければ飛行機、一番安く移動したければ夜行バスが最適な移動方法になるかと思います。

時間的最適と空間的最適

アルゴリズムはよくコンピュータの計算方法という意味で使われます。 この場合における最適なアルゴリズムとは以下の点を満たしたもののことを言います。

  • 演算回数が少ない(時間的に最適)
  • メモリ消費が少ない(空間的に最適)

演算とは足し算、かけ算のことで、演算回数が少なければ早く問題を解くことができます。 メモリとは、コンピュータが演算するために必要な記憶領域のことです。コンピュータはメモリ領域が決まっているため、少ないメモリ消費で問題が解ければ、同時に他の問題を解くことができるため良いアルゴリズムといえます。

1つの問題を早く解きたい場合は演算回数が少ないアルゴリズム、多くの問題を同時に解きたい場合はメモリ消費が少ないアルゴリズムが最適だといえます。

問題1:1から3までの和を求める2つの方法

今回は時間的に最適なアルゴリズムについて考えてみましょう。ここでの最適なアルゴリズムとは、演算回数が一番少ないアルゴリズムです。

問題. 1から3までの和を求めよ。

まず、1から3までの計3個の数字の和を求める問題です。答えは6です。 さて、皆さんはどのようにこの答えを導き出したでしょうか? 以下にアルゴリズム(計算方法)を2つほど挙げてみましょう。

アルゴリズム

アルゴリズム1はとっても単純です。素直に1から3まで足し算します。

1+2+3=6

小学生でもわかりますね。 このアルゴリズムにおける演算回数は足し算のみの 2回です。

アルゴリズム

アルゴリズム2では少し変わった計算をしてみます。


\begin{align}
\sum_{k=1}^ {3}k = \frac{1}{2} \times 3 \times (3 + 1) =6
\end{align}

1, 2, 3を数列a_{n}=nと捉えて、数列の和の公式を用いて求めています。

和の公式: 
\begin{align}
\sum_{k=1}^ {n}k = \frac{1}{2} \times n \times (n + 1)
\end{align}

このアルゴリズムの演算回数は、足し算1回とかけ算2回の計3回です。

問題2:1から100の和を求める2つの方法

問題1ではアルゴリズム1が最適なアルゴリズムでした。さて、次の問題ではどうでしょう?

問題. 1から100までの和を求めよ。

今度は1から100までの計100個の数字の和を求める問題です。答えは5050です。先ほどと同様に2つのアルゴリズムについてみていきましょう。

アルゴリズム

先ほどと同様に、素直に1から100まで足し算をします。

1+2+\dots +99+100=5050

うむ、非常にめんどくさい😅小学生でもできると思いますが、とにかくめんどくさいw

演算回数は先ほどより大きく増えて 99回の足し算が必要です。 アルゴリズム1は、数字の個数が増えるほど演算回数が増えるという特徴がありますね。

アルゴリズム

アルゴリズム2では数列の和の公式を用いて計算をします。


\begin{align}
\sum_{k=1}^ {100}k = \frac{1}{2} \times 100 \times (100 + 1) =5050
\end{align}

あぁ、なんて楽なんだ。笑

演算回数は、足し算1回とかけ算2回の計3回です。 そうなんです、さっきと同じ演算回数なんです! アルゴリズム2は数字の個数が増えても演算回数が変わらないという特徴があり、これは最高な利点です。

計算量(オーダー)について

時間的に最適なアルゴリズムについて考えてきました。 アルゴリズムの世界には計算量(オーダー)という概念が存在するため紹介します。計算量とは 対象の個数と演算回数の関係を表したものです。計算量を見るだけで「早いアルゴリズムかどうか」を一瞬で判断することができます。

先ほどの和を求める問題を例にして説明します。 ここでの対象の個数とは足し算をする数字の個数です。 この値を n とします。 問題1では n=3 、問題2では n=100 となります。

演算回数を f(n) とします。これは、演算回数を対象の個数の関数で表しています。 アルゴリズム1の演算回数は、問題1では2回、問題2では99回でした。 つまり、 f(n)=n-1 と表すことができ、n におおよそ比例して演算回数が大きくなっていることがわかります。 この時、計算量はO(n)と表されます。

一方、アルゴリズム2の演算回数は、問題1と問題2ともにに3回でした。 つまり、 f(n)=3 と表すことができ、n の値に関係なく演算回数は一定であることがわかります。 この時、計算量はO(1)と表されます。

このように、計算量はO(nの式)で表されます。 計算量が同じアルゴリズムであれば、問題を解く速さは大体同じです。 最速はもちろんO(1)ですね。O(1)アルゴリズムで問題が解けると知った時、エンジニアはみんな興奮します、いやホントに(笑)

計算量を早い順に並べると以下のようになります(スマートフォンの方は横向きでご覧ください。


\begin{align}
(速い)O(1)\rightarrow O(\log n)\rightarrow O(n)\rightarrow O(n\log n)\rightarrow O(n ^2)\rightarrow O(2 ^n)\rightarrow O(n!)(遅い)
\end{align}

アルゴリズム、奥が深い。

おわりに

今回はアルゴリズムについてのお話でした。 アルゴリズムは計算方法のことで、問題をどのように解くかを表したものです。

最適なアルゴリズムには

  • 時間的最適
  • 空間的最適

というものがあります。 計算量の概念にも軽く触れました。

代表的なアルゴリズムについての話もできればと思うので乞うご期待!

というわけでみなさん、

アルゴリズムをはじめましょう←

ではでは。

ハローアルゴリズム

ご指摘、ご意見などがあれば、コメントお願いします。またTwitterのDMにでもご連絡いただけたらと思います。 よしデブ(@yoshidev523)| Twitter

初めまして

Who?

こんにちは、yoshidev(よしデブ)です。

大学時代はIoT分野でスマートホームでの行動認識の研究をやってまして、今はWeb系企業のエンジニアとして働いておりやす👨‍💻

何を書く?

基本的には自分の趣味/仕事であるIoT、Web、プログラミングに関することを記事にしようかなと思っています!

また、上記に関する自分の制作物の紹介もするかもしれません。

またまた、たわいもないネタ話もあるかも?多くなってきたらコンテンツのシリーズ化とかできたらいいなと思ってます🤔

意気込み

頑張るべ