这个循环的时间复杂度是多少?带迭代器的while循环的复杂度为O(n),但由于它也具有对其他某些类的函数调用。该函数有一个for循环,仅用于读取列表和if / else条件。我很困惑复杂度是否保持在O(n)还是会增加?因为for循环由来自while的n个对象组成,所以如果我仅考虑这一点,则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 ....
}
}
}
谢谢!
没有足够的信息来计算时间复杂度。它取决于构造函数是否AnotherClass()
取决于任何相关参数(例如,全局变量或其他输入)以及的行为AnotherClassfunction()
。但是,即使while循环的主体完全为空,复杂度也不一定是O(count(it))
。这取决于迭代器的实现。
例如,的成本很可能AnotherClassfunction(tp)
取决于的大小tp
。在这种情况下,时间复杂度将不仅仅取决于长度it
,还取决于的大小内容的it
,所以它甚至可能是一个多元函数。
假定的成本AnotherClassFunction
是长度indepedendentn
的it
并且仅依赖于它的输入参数的大小tp
,并且假定所有元素tp
的it
具有相同的尺寸m
,并假设迭代it
为O(n),并假设时间复杂度的AnotherClassFunction
由函数给出g
,该环路的总的复杂性是有两个参数是在一个功能O(n*g(m))
。
我已经用AnotherClassFunction更新了问题.. tp的大小不固定,因为它取决于查询的大小。“它”具有从查询字符串读取的(节点,路径,节点)。是多元函数吗?
是的,这似乎取决于许多其他功能,
getObject
,getSubject
,matches
,等你粘贴代码不编译。那么,上述多元函数的时间复杂度大概是多少?因为我对它的了解较少。
@fairyjee我已经更新了答案-您知道,有很多假设...
这个假设接近我在做什么。它的元素tp具有相同的大小。这是有道理的。谢谢你。