88571


計算量の話題でクイックソートはO(nlogn)などありますが、あるアルゴリズムが複雑で計算量のオーダーを論理的に出すのが難しいとき、計算時間の実測値（入力のサイズを色々変えて計算時間を計る）からオーダーを推測するような手法はあるでしょうか？


CC BY-SA 4.0
2022-04-28T06:49:08.027
88547
2022-04-30T07:43:41.050
18637
question
計算量
計算量のオーダーを実測値から推測する。


正確に推定するのは難しいです。

まず前提として、ランダウの記号を使った時間計算量の表記は漸近的な挙動を考えるのに使うものであり、もし質問者さんの持っている課題が特定の未知の入力に対する時間計算量（実行時間）を推定したいだけなのであれば、漸近的な挙動を求めなくても実測値から未知の実行時間を直接推定できないか考えることができます。

特に、入力が "小さい" ときの実行時間しか測れず、それらのデータを元に入力が "大きい" ときの実行時間を推測したくなることはよくあります。

この場合のひとつの手法として、統計的に外挿するという方法はあります。ただし時間計算量について何の仮定もおけないのであれば、フィッティングしたい目的の関数が指数的な挙動を含む可能性があり、推定が難しくなるでしょう。また、入力がごく
"小さい" ときのデータしか手元に無い場合、色々な関数がフィットしうるので、推定するのが根本的に難しい問題になります。

別の方法として、ソースコードを元に時間計算量を静的解析するという方向で考えることもできます。ただ、研究レベルでは色々結果が知られており一部の結果は産業界でも使われている一方で、複雑な解析はまだ難しい印象で、人間が解析しづらいコードであるなら現状あまり期待しづらいです。興味があればたとえばソフトウェアとしては
[Infer](https://fbinfer.com/docs/checker-cost/) が知られています。


CC BY-SA 4.0
2022-04-29T16:50:23.090
88571
2022-04-30T07:43:41.050
2022-04-30T07:43:41.050
19110
19110
88547
answer