複合関数で計算されたアルゴリズムの複雑度

Question

複合関数で計算された複雑さの論理式はありますか？ 私はfがO（n^2）に属し、gがO（n）に属しているとしましょう。複雑さがf（g（n））、魔女がO（n^2）のアルゴリズムがありますか？

Answer 1

私は実際にこのケースに会ったことはありませんが、そのようなアルゴリズムは想像できます。たとえば、実行時に別のアルゴリズムを分析するアルゴリズム。たとえば、比較ベースのソートアルゴリズムや、実行されたすべての比較結果を保存し、時間を測定し、ソートしたり、いくつかの統計を実行したりするアルゴリズムアナライザなどがあります。第2アルゴリズムの複雑さは、f(n)それがエントリーとして取得され、ソートアルゴリズムがg(n)の複雑さを有する場合、サイズnの入力に対するソートアルゴリズムの分析を実行すると、合計複雑度はf(g(n))となります。

とにかくnは、f(n)とg(n)では同じことではないことが明らかです。基本的にアルゴリズムalgo2を、その複雑さとほぼ同じサイズのalgo1の出力に実行すると動作します。