以下代碼的大運行時間是多少？

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你會得到它。