一般的には、システムの環境を考慮したうえで、時間計算量と領域計算量のトレードオフやバランスを考えてアルゴリズムを設計する
- 時間計算量：プログラムの実行に必要な時間
- 領域計算量：プログラムの実行に必要な記憶領域
O表記法：アルゴリズムの効率を評価するものさしのひとつ メリット：計算量を求めることで２つのアルゴリズムの性能を比較することが可能になる
- O(1)：データ数nにかかわらず一定なので、nが2倍、3倍、10倍となっても計算量は等しいまま
- O(n)：nが2倍、3倍と増えると、計算量も同様に2倍、3倍となる
- O(log n)：nが2倍、3倍と増えても、計算量は1、2と増える程度なのでデータ量が多い場合に有用
- O(n log n)：O(log n)にnの計算量がかけられたもの
-
O(2 n乗),O(n!)（!は階乗）のアルゴリズムはnが大きくなると計算量が莫大になるので避ける
-
計算量が数百万から数千万程度であれば数秒以内で処理を行うことができる
-
計算量の求め方
- 手順１）各行のステップ数を求める
- 手順２）プログラム全体のステップ数を求める
- 手順３）不要なものを除く
-
注意）計算量による比較は万能ではない
- 計算量は、入力サイズが小さい場合や定数倍程度の違いを考慮に入れていません
開発新卒に捧ぐ、基本のアルゴリズムと計算量
https://www.techscore.com/blog/2016/08/08/%E9%96%8B%E7%99%BA%E6%96%B0%E5%8D%92%E3%81%AB%E6%8D%A7%E3%81%90%E3%80%81%E5%9F%BA%E6%9C%AC%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%A8%E8%A8%88%E7%AE%97%E9%87%8F/
[初心者向け] プログラムの計算量を求める方法
https://qiita.com/cotrpepe/items/1f4c38cc9d3e3a5f5e9c
整数の階乗
https://naop.jp/topics/topics38.html