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)然后是第二个 while O(n)还有 if O(n) = O(n^3) 。不知道我是不是错了？

Answer 1

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