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)
,然后是第二个whileO(n)
和if也O(n) = O(n^3)
。我不知道我是否错了
# 1 楼答案
毫无疑问@史蒂文给出了一个很好的数学表示。这里发生的大O是提供给该方法的列表大小的乘法
因为
list1
中的每个元素都在与list2
中的每个元素进行比较。。这样循环就为SizeofList1*SizeOfLit2
运行这里是带有循环的beginner guide。希望你能得到它
# 2 楼答案
是
O(size(lst1)*size(lst2))
。对于lst1
中的所有xi,将xi与lst2
中的每个元素进行比较。在本例中,它更准确地是Θ(size(lst1)*size(lst2))
,因为它的上下边界都是size(lst1)*size(lst2)