While与另一类函数调用的时间复杂性

Question

这个循环的时间复杂度是多少？带有迭代器的while循环的复杂性是O(n(，但由于它还有一个对其他类的函数调用。该函数有一个for循环，仅用于读取列表和if/else条件。我很困惑复杂性是保持在O(n(中，还是会增加？因为循环由n个对象组成，而如果我只考虑这一点，那么循环的复杂性是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的内容的大小，因此它甚至可能是一个多变量函数。

---

根据评论更新：

假设AnotherClassFunction的代价独立于it的长度n，并且仅取决于其输入自变量tp的大小，并且假设it的所有元素tp具有相同的大小m，并且假设在it上迭代是O(n(，并且假设由函数g给出AnotherClassFunction的时间复杂度，循环的总复杂度是CCD_ 18中的具有两个自变量的函数。