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

Question

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;
}

1. 如果为lst1和lst2传递了ArrayList
2. 如果为lst1和lst2传递了LinkedList

我选择两者，因为对于第一个while循环O(n)，然后是第二个whileO(n)和if也O(n) = O(n^3)。我不知道我是否错了

Answer 1

毫无疑问@史蒂文给出了一个很好的数学表示。这里发生的大O是提供给该方法的列表大小的乘法

因为list1中的每个元素都在与list2中的每个元素进行比较。。这样循环就为SizeofList1*SizeOfLit2运行

这里是带有循环的beginner guide。希望你能得到它

Answer 2

是O(size(lst1)*size(lst2))。对于lst1中的所有x_i，将x_i与lst2中的每个元素进行比较。在本例中，它更准确地是Θ(size(lst1)*size(lst2))，因为它的上下边界都是size(lst1)*size(lst2)