計算量の話題でクイックソートはO(nlogn)などありますが、あるアルゴリズムが複雑で計算量のオーダーを論理的に出すのが難しいとき、計算時間の実測値(入力のサイズを色々変えて計算時間を計る)からオーダーを推測するような手法はあるでしょうか?
1 件の回答
正確に推定するのは難しいです。
まず前提として、ランダウの記号を使った時間計算量の表記は漸近的な挙動を考えるのに使うものであり、もし質問者さんの持っている課題が特定の未知の入力に対する時間計算量(実行時間)を推定したいだけなのであれば、漸近的な挙動を求めなくても実測値から未知の実行時間を直接推定できないか考えることができます。
特に、入力が "小さい" ときの実行時間しか測れず、それらのデータを元に入力が "大きい" ときの実行時間を推測したくなることはよくあります。
この場合のひとつの手法として、統計的に外挿するという方法はあります。ただし時間計算量について何の仮定もおけないのであれば、フィッティングしたい目的の関数が指数的な挙動を含む可能性があり、推定が難しくなるでしょう。また、入力がごく "小さい" ときのデータしか手元に無い場合、色々な関数がフィットしうるので、推定するのが根本的に難しい問題になります。
別の方法として、ソースコードを元に時間計算量を静的解析するという方向で考えることもできます。ただ、研究レベルでは色々結果が知られており一部の結果は産業界でも使われている一方で、複雑な解析はまだ難しい印象で、人間が解析しづらいコードであるなら現状あまり期待しづらいです。興味があればたとえばソフトウェアとしては Infer が知られています。
-
-
特に計算量に限った話ではなく一般の外挿をする想定で書いていました。つまりよくある統計処理ソフトウェアならたいていそういった機能が付いています。ただいずれにしてもある程度目的関数の形を決めてからでないと推定は難しいはず……です。– nekketsuuu ♦Commented 2022年4月30日 7:46