While 的时间复杂度与另一个 class 的函数调用

Question

这个循环的时间复杂度是多少？带有迭代器的 while 循环的复杂度是 O(n)，但因为它也有一个函数调用以及其他一些 class。该函数有一个 for 循环，仅用于读取列表和 if/else 条件。我很困惑复杂性是保持在 O(n) 还是会增加？因为 for 循环由 n 个从 while 获得的对象组成，所以如果我只考虑这一点，那么 for 循环的复杂度是 O(m) 和 m+n = n 。但我不确定这是否有意义。

 public static void main(String[] args) {
    final String queryString  = "" +
        "SELECT ?a WHERE {\n" +
        " ?a ?b ?c1 ;\n" +
        " ?e ?b ?c2 .\n" +
        "}";
    final Query query = QueryFactory.create( queryString );
    System.out.println( "== before ==\n"+query );
    ElementWalker.walk( query.getQueryPattern(), 
            new ElementVisitorBase() {
                @Override
                public void visit(ElementPathBlock el) {
                    ListIterator<TriplePath> it = el.getPattern().iterator();
                    while ( it.hasNext() ) {
                        final TriplePath tp = it.next();
                        AnotherClass ac = new AnotherClass();
                        ac.AnotherClassfunction(tp);
                        }
                    }
                }
    });

另一个班级

   final static Set<Node> objects = new HashSet<Node>();
   static void AnotherClassFunction(TriplePath tp,)
   {
       Node Object  = tp.getObject();  
       Node Subject = tp.getSubject();      
       objects.add(tp.getObject());
       for(Node o: objects) {
           if(Subject.matches(o)) {
           print ....
    }
    }
    }

谢谢！

Answer 1

没有足够的信息来计算时间复杂度。这取决于构造函数 AnotherClass() 是否依赖于任何相关参数（例如全局变量或其他输入），以及 AnotherClassfunction() 的行为。但即使 while 循环体完全为空，复杂度也不一定是 O(count(it))。这取决于迭代器的实现。

例如，AnotherClassfunction(tp) 的成本很可能取决于 tp 的大小。在那种情况下，时间复杂度不仅取决于 it 的长度，还取决于 it 的 contents 的大小，因此它甚至可能是多元函数。

根据评论更新：

假设 AnotherClassFunction 的成本与 it 的长度 n 无关，仅取决于其输入参数的大小 tp，并假设it 的所有元素 tp 具有相同的大小 m，并假设迭代 it 是 O(n)，并假设 AnotherClassFunction 的时间复杂度] 由函数 g 给出，循环的总复杂度是在 O(n*g(m)).

中的具有两个参数的函数

While 的时间复杂度与另一个 class 的函数调用

Time Complexity of While with function call of another class

java

ontology

time-complexity

根据评论更新：