3

ここに画像の説明を入力してください

上記のモデルがフェイステーブルリストに表示されています。ここで、F1, F2,...F_nはモデルの面であり、それらの面番号はリスト配列のインデックスです。各リスト要素は、3つの頂点の別の配列です。x,y,zまた、各頂点は、その座標を表す3つの整数の配列です。

座標を持つ頂点のすべての隣接する面を見つけたいです(x2, y2, z2)。私はこのタスクを実行すると信じているこのコードを思いついた：

List faceList;   //say the faceList is the table in the picture above.
int[] targetVertex = {x2, y2, z2};   //say this is the vertex I want to find with coordinates (x2, y2, z2)
List faceIndexFoundList; //This is the result, which is a list of index of the neighbouring faces of the targetVertex

for(int i=0; i<faceList.length; i++) {
   bool vertexMatched = true;
   for(int j=0; j<faceList[i].length; j++) {
      if(faceList[i][j][0] != targetVertex[0] && faceList[i][j][1] != targetVertex[1] && faceList[i][j][2] != targetVertex[2]) {
         vertexMatched = false;
         break;
      }
   }
   if(vertexMatched == true) {
      faceIndexFoundList.add(i);
   }
}

タスクを実行するための複雑さはO（N ^ 2）であると言われました。しかし、私が持っているコードでは、O（N）だけのように見えます。targetVertexポリゴンごとに頂点が3つしかないため、の長さは3です。したがって、2番目の内部ループは単なる定数です。次に、外側のループだけを残しました。外側のforループはO（N）のみです。

上記のコードの複雑さは何ですか？私は何を間違えたのでしょうか？

4

3 に答える 3

2

複雑さは (おおよそ) faceList.length * faceList[i].length であり、これらは独立していますが、どちらも非常に大きくなる可能性があり、大きくなるにつれてそれぞれが無限大に近づき、その時点で (概念的に) n に収束し、その結果、複雑さは O(n^2)

頂点リストが明示的に 3 に制限されている場合、複雑さは faceList[i].length * 3、つまり O(n) になります。

于 2012-08-23T20:23:02.103 に答える
1

最悪の場合、各ポリゴンの各頂点を見なければならないことは明らかです。

これは、投稿の O(テーブルのサイズ) にすぎません。これは、すべての行の長さの合計またはすべてのポリゴンの頂点数の合計のどちらか好きな方です。

ポリゴンの頂点数が m 以下でポリゴン数が n である場合、アルゴリズムは O(mn) です。

FWIW より洗練されたデータ構造を使用すると、まったく検索せずに答えを得ることができます。たとえば、winged edge データ構造などを参照してください。この場合、関心のある頂点に移動し、隣接するすべてのポリゴンを接続するリンクをトラバースするだけです。出力の各ポリゴンのコストは一定です。

ポリゴン メッシュ用のこれらの洗練されたデータ構造は、頻繁に使用される多くの操作を驚くほど効率的にサポートします。

于 2012-08-27T00:47:44.977 に答える
0

ウィキペディアから：

Big O 記法は、引数が特定の値または無限大に向かう傾向がある場合の関数の制限動作を記述するために使用されます。

forこの 1 つのケースでは、1 つのループしか実行していない可能性があります。しかし、多角形の頂点の数が無限に近づくとどうなるでしょうか? ほとんどの場合、2 番目のforループが実行されますか、それとも壊れますか? これにより、関数がO(n)またはであるかどうかが決まりますO(n^2)。

于 2012-08-19T05:06:15.843 に答える