graphics - 这段代码的复杂度是多少？

Question

我有一个在面表列表中表示的上述模型，其中 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)。

我上面的代码有多复杂？我可能做错了什么？

Answer 1

复杂度(近似)是 faceList.length * faceList[i].length，它们是独立的，但都可以变得非常大，并且随着它们的增长，它们将各自趋近于无穷大，此时(概念上)它们将收敛于n，导致复杂度为 O(n^2)

如果顶点列表明确限制为3，那么复杂度就变成了faceList[i].length * 3，也就是O(n)