java - Big-O 运行时确定 List 是否包含 X 和 F(X)

Question

我试图了解以下方法的大 O 是什么。

    for(Integer i : list){
        if(list.contains(-i))
            //doSomething
    }

我知道 contains 方法是 O(n)，而像这样的 for 循环也是 O(n)。这是否使此方法的总数为 O(n * n)？

Answer 1

假设List.contains是O(n)，那么是的，整个算法是O(n^2)。

Answer 2

但是，如果您在列表中使用迭代器并使用 hasNext 方法，那么最坏情况下的总运行时间将大 O(n)。近似公式将是一个常数加上 n，其中 n 是 if 条件。与 for 循环不同，迭代器需要一个恒定的时间来返回一个对象。

Answer 3

因此，假设 m 和 n 是两个列表，那么总运行时间将为 n+1m+2m+...+(n-n+1)m。