3

在此处输入图像描述

我在 Face Table List 中表示了上述模型，其中F1, F2,...F_n是模型的面，它们的面号是列表数组的索引。每个列表元素是另一个包含 3 个顶点的数组。每个顶点是一个由 3 个整数组成的数组，表示其x,y,z坐标。

我想用坐标找出顶点的所有相邻面(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 个顶点。所以，第二个内循环只是一个常数。然后，我只留下了外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 可以使用更复杂的数据结构完全无需搜索即可获得答案。参见例如有翼边缘数据结构等。在这种情况下，您只需转到您感兴趣的顶点并遍历连接所有相邻多边形的链接。输出中每个多边形的成本是恒定的。

这些用于多边形网格的更高级的数据结构以出色的效率支持许多常用操作。

于 2012-08-27T00:47:44.977 回答
0

来自维基百科：

大 O 表示法用于描述当参数趋于特定值或无穷大时函数的限制行为。

在这种情况下，您可能只运行一个for循环。但是当多边形的顶点数接近无穷大时会发生什么呢？大多数情况会导致第二个for循环运行还是中断？这将确定您的函数是O(n)还是O(n^2)。

于 2012-08-19T05:06:15.843 回答