1

コードの複雑さの分析の一部として確率関数をどのように組み込むことができますか。

if (cond1(l,n)) {
   for (int r=l;r<n;r++)
      for (int m=r;m<n;m++)
          for (int k=m;k<n;k++)
               //calculation
} else
    // calculation

このコードの典型的な複雑さの分析は、複雑さを O(N^3) として生成します。

cond1(l,n) が大幅に false を生成するため、仮想計算で内側の for ループをスキップするとします。

一連の同様のアルゴリズムの複雑さを比較したいので、コードの複雑さをできるだけ正確に計算したいと考えています。

たとえば、cond1(l,n) を、内側のループ呼び出しを減らす別のアルゴリズム セットに置き換えたいとします。

アルゴリズムの複雑さをできるだけ正確に計算するにはどうすればよいですか。

私が分析しようとしているコードの現実的なシナリオは [link] Analyzing a exponential recursive function にあります。

4

1 に答える 1

0

複雑さの分析は、ここでの作業に適したツールではありません。問題の規模が拡大するにつれて何が起こるかを大まかに把握することを目的としています。ランタイムの正確な分析を探している場合は、代わりにコードのベンチマークまたはプロファイリングを行います。

于 2014-03-29T04:27:12.827 に答える