java—while的时间复杂度,函数调用另一个类

sqyvllje  于 2021-07-03  发布在  Java
关注(0)|答案(1)|浏览(479)

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

谢谢你!

w1e3prcc

w1e3prcc1#

没有足够的信息来计算时间复杂度。这取决于构造函数 AnotherClass() 取决于任何相关参数(如全局变量或其他输入),以及 AnotherClassfunction() . 但是,即使while循环的主体是完全空的,复杂性也不一定是空的 O(count(it)) . 这取决于迭代器的实现。
例如,很可能 AnotherClassfunction(tp) 取决于 tp . 在这种情况下,时间复杂性将不仅仅取决于时间长度 it ,还取决于内容的大小 it ,所以它甚至可能是一个多元函数。

根据评论更新:

假设 AnotherClassFunction 与长度无关 nit 只取决于输入参数的大小 tp ,并假设所有元素 tpit 大小相同 m ,假设 it 是o(n),假设 AnotherClassFunction 由函数给出 g ,循环的总复杂度是一个包含两个参数的函数 O(n*g(m)) .

相关问题