【独習】アルゴリズムの実行時間の評価方法

アルゴリズムの実行時間の評価方法を理解しているだろうか。

アルゴリズムについては、そして正しいアルゴリズムについては、過去記事から理解していることだろう。
では、そのアルゴリズムの実行時間の評価方法の説明ができるだろうか。
今回は、アルゴリズムの実行時間の評価方法を書き溜め、
新しく計算機科学を学ぶ人のためのマイルストーンを残していく。

広告

アルゴリズムの実行時間の評価方法

多くの場合、ある問題を解くための正しいアルゴリズムは複数ある。
どのアルゴリズムを採用すれば、効率的に解を得られるかを判断し評価する必要がある。
そのためには、アルゴリズムを評価するための尺度が求められる。

評価するための尺度として代表的なものとして
「計算量(アルゴリズム計算量)」というものがある。
計算量は、計算の複雑さ(complexity)を示している。

計算量の中にも評価軸が2種類ある。

  • 時間計算量
  • 領域計算量

時間計算量

時間計算量とは、
プログラムの実行が開始されてから終了するまでにかかったCPUの処理時間を集計した値のことである。
つまり、アルゴリズムを実行するときに消費する時間であり、ステップ数などとして表現される。

領域計算量

領域計算量とは、
プログラムの実行が開始されてから、終了するまでに使用された記憶領域の容量を集計した値のことである。
つまり、アルゴリズム処理に必要な空間的な領域の大きさであり、ビット、バイトなどとして表現される。


「時間計算量」「領域計算量」ともに計算量であり
少なければ少ないほど良いアルゴリズムであるということである。

アルゴリズムの実行時間の評価方法を説明してください。

さて、先程の説明を読んだ人は、アルゴリズムの実行時間の評価方法を説明できますね。
代表的な尺度がありましたね?覚えてますか?

ノートやメモに書くでも、Twitterに呟くでもYoutubeにアップロードするでも構いません。
今日知った情報をアウトプットしてみましょう。


じゃあね〜〜〜。