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

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. 如果ArrayList传递给lst1和lst2。
2. 如果LinkedList传递给lst1和lst2。

我去，因为两者的拳头while循环O(n)然后同时O(n)的secong和如果还O(n) = O(n^3)。我不知道我是否错了？

Answer 1

这是O(size(lst1)*size(lst2))。对于所有x _i in lst1，您将x _i与lst2中的每个元素进行比较。在这种情况下，它更准确地说是Θ(size(lst1)*size(lst2))，因为它的上下都有size(lst1)*size(lst2)。

Answer 2

毫无疑问.. @steven给了一个不错的数学代表。发生在这里的大O是为该方法提供的列表大小的乘积。

因为list1中的每个元素都与list2中的每个元素进行比较。因此循环运行的时间为SizeofList1*SizeOfLit2。

这里是beginner guide与loops.Hope你会得到它。