java - 以下代码的最大O运行时间是多少？

public static int Count( List<Integer> lst1, List<Integer> lst2)
{
    Iterator<Integer> itr1 = lst1.iterator();

    int count=0;
    while ( itr1.hasNext() )
    {
        Integer x = itr1.next();
        Iterator<Integer> itr2 = lst2.iterator();
        while ( itr2.hasNext() )
            if ( x.equals( itr2.next()) )
                count++;
    }

    return count;
}

如果为lst1和lst2传递了ArrayList。
如果为lst1和lst2传递了LinkedList。


我都选择这是因为对于拳头while循环O(n)然后是secong while O(n)和if if O(n) = O(n^3)。我不知道我是否错了？

最佳答案

是O(size(lst1)*size(lst2))。对于lst1中的所有xi，请将xi与lst2中的每个元素进行比较。在这种情况下，它更准确地是Θ(size(lst1)*size(lst2))，因为它在上下两面都受size(lst1)*size(lst2)限制。

关于java - 以下代码的最大O运行时间是多少？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/17255880/