6

コードの 2 つのセクションの循環的複雑度を知りたいのですが、

IF((A>B) AND (C>D)) 
{ a=a+b;c=c+d;}

私の知る限り、上記のコードの循環的複雑度は= 2 + 1 = 3です。

別のコード

IF((A>B) OR (C>D))
{a=a+b;c=c+d;}

上記のコードの複雑さは=4+1=5、

上記の複雑さが正しいかどうか？

4

2 に答える 2

11

両方の複雑さは同じで、3 に等しく、4 つの方法で数えられます。De Morganを使用してそれらが同じであることを証明することについてNeilに同意します。複雑さのカウントに重要なグラフから同じことがわかると思います。

グラフ

両方のコード部分のグラフから始めましょう。

+ または

+ の場合

説明の言葉:

  1. McCabe グラフは基本的なブロックで構成されています。つまり、コントロールがそれらの間を直線的に通過する限り、多くのステートメントを 1 つに折りたたむことができます。
  2. 私はあなたのコードを単純な手順、1 つの入口点、1 つの出口点として扱いました。
  3. 終了点は、すべてが終了するシンクとして追加されます。McCabe 計算のコードからグラフを作成する例はほとんどなく、覚えている例もありませんが、基本ブロックとは何か、ノード/エッジとは何かを考えると、これは自然なことだと思います。
  4. 出口と入口の間のエッジは、複雑な計算を単純化するためにのみ関連するため、メモと異なるマーキング (色、矢印) が使用されます。
  5. 基本ブロックは、非線形に制御を渡す可能性のある命令 (while、for、if など) によって区切られます。
  6. McCabe 自身を引用すると、AND と OR は複雑さに +1 を追加します。これらは基本的にif and ifandif or ifであるため、2 つの if です。したがって、私の2番目のノードは別のノードです。

ご覧のとおり、両方のコード片に数字の違いはありません。ノード、エッジ、リージョンはすべて同じです。違いは、どのノードがどのノードに接続するかであり、これは短絡のしくみに由来します。明らかに、それを持たない言語の場合、グラフは異なる必要があります。

複雑性の定義

複数あります。複雑さは等しい

エッジ - ノード + 2*(出口)

エッジ = 5; ノード = 4; 出口 = 1;

どちらの場合も、複雑さ = 5-4+2*(1) = 3 です。この定義は強く接続されたグラフを必要としないため、追加されたエッジを削除します。

エッジ - ノード + 出口は、強く接続されたグラフを提供します

エッジ = 6; ノード = 4; 出口 = 1;

どちらの場合も、複雑さ = 6-4+1 = 3 です。この定義は、トポロジー的により意味があり、循環カウント (グラフ単位) の観点から考えるのがより簡単であるためです。クラス内のすべてのメソッドのように、多くのルーチン/関数の複雑さを数えることを考えると、より便利です。関数がループで呼び出される可能性があると考えるのは理にかなっています。しかし、私は脱線します。

地域

地域: 3.

これは、領域 + ノード - エッジ = 2 というオイラー式から来ています。これを言い換えると: 領域 = エッジ - ノード + 2

したがって、領域の数は複雑さと同じです (1 つの出口点を想定)。これは、1 回の終了サブルーチンで、グラフからの複雑さのカウントを簡素化することを目的としていました。

決定点 + 1

マッケイブ自身は次のように述べています。

実際には、IF "c1 AND c2" THEN などの複合述語は、結合詞 AND がなければ IF c1 THEN IF c2 THEN が 2 つの述語を持つため、複雑さに 2 を与えるものとして扱われます。この理由とテストの目的で、複雑さを計算するときに述語ではなく条件をカウントする方が便利であることがわかっています。

両方のコード部分に 1 つの複合条件があるため、Decisions = 2;

複雑さ = 2+1 = 3。

サイクロマティックな複雑さはサイクルをカウントすることから始まり、実用的な目的で条件をカウントすることで終わったことは注目に値します。

参考文献

最初に McCabe の論文自体を試してください: http://www.literateprogramming.com/mccabe.pdf

ウィキペディアにはこの論文に基づいた優れた記事がありますが、基本ブロックと接続コンポーネントに従わないと不十分であることがわかりました。

  1. http://en.wikipedia.org/wiki/Cyclomatic_complexity
  2. http://en.wikipedia.org/wiki/Basic_block
  3. http://en.wikipedia.org/wiki/Connected_component_(graph_theory)

Chambers のページで簡潔でありながら優れた要約を見つけました: http://www.chambers.com.au/glossary/mc_cabe_cyclomatic_complexity.php

第8章の本「ソフトウェアエンジニアリングへの統合アプローチ」には、複雑さの計算を示す例があります（グラフの1つのエッジを食べたと思いますが、図8.7）。

http://books.google.pl/books?id=M-mhFtxaaskC&lpg=PA385&ots=jB8P0avJU7&d&hl=pl&pg=PR1#v=onepage

于 2014-02-09T11:03:25.087 に答える
3

私はそれらが 3 という同じ循環的複雑度を持っていると思います。これは、ド・モルガンの法則を使用して示すことができます。

IF((A>B) OR (C>D)) {a=a+b;c=c+d;} ELSE {}

IF(!((A>B) OR (C>D))) {} ELSE {a=a+b;c=c+d;}

IF(!(A>B) AND !(C>D)) {} ELSE {a=a+b;c=c+d;}

それを見る別の方法は、グラフを取得して条件付きブロックと出口点を交換し (そしてそれらの間のエッジを反転させ)、ノードまたはエッジの数を変更せずに AND から OR に変換することです。

于 2012-09-26T11:10:28.090 に答える