Warm tip: This article is reproduced from serverfault.com, please click

java-While的时间复杂度与另一个类的函数调用

(java - Time Complexity of While with function call of another class)

发布于 2020-11-28 18:44:44

这个循环的时间复杂度是多少?带迭代器的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 ....
    }
    }
    }

谢谢!

Questioner
fairyjee
Viewed
0
Mo B. 2020-11-29 04:57:26

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

例如,的成本很可能AnotherClassfunction(tp)取决于的大小tp在这种情况下,时间复杂度将不仅仅取决于长度it,还取决于的大小内容it,所以它甚至可能是一个多元函数。


根据评论更新:

假定的成本AnotherClassFunction是长度indepedendentnit并且仅依赖于它的输入参数的大小tp,并且假定所有元素tpit具有相同的尺寸m,并假设迭代it为O(n),并假设时间复杂度的AnotherClassFunction由函数给出g,该环路的总的复杂性是有两个参数是在一个功能O(n*g(m))