这个循环的时间复杂度是多少?带迭代器的while循环的复杂度是o(n),但因为它有一个函数调用以及其他一些类。该函数有一个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 ....
}
}
}
谢谢你!
1条答案
按热度按时间w1e3prcc1#
没有足够的信息来计算时间复杂度。这取决于构造函数
AnotherClass()
取决于任何相关参数(如全局变量或其他输入),以及AnotherClassfunction()
. 但是,即使while循环的主体是完全空的,复杂性也不一定是空的O(count(it))
. 这取决于迭代器的实现。例如,很可能
AnotherClassfunction(tp)
取决于tp
. 在这种情况下,时间复杂性将不仅仅取决于时间长度it
,还取决于内容的大小it
,所以它甚至可能是一个多元函数。根据评论更新:
假设
AnotherClassFunction
与长度无关n
的it
只取决于输入参数的大小tp
,并假设所有元素tp
的it
大小相同m
,假设it
是o(n),假设AnotherClassFunction
由函数给出g
,循环的总复杂度是一个包含两个参数的函数O(n*g(m))
.