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)然后是 secong whileO(n)和 if 也是O(n) = O(n^3)。我不知道我是不是错了？

Answer 1

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

Answer 2

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

因为 with 中的每个元素都与 .. 中的list1每个元素进行比较list2，所以循环运行 for SizeofList1*SizeOfLit2。

这是带有循环的初学者指南。希望你能得到它。