Big-O 运行时，用于确定列表是否包含 X 和 F(X)

Question

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

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

我知道包含方法是 O（n），像这样的 for 循环也是 O（n）。 这是否使此方法的总数为 O（n * n）？

Answer 1

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

Answer 2

BUt 如果你在列表中使用迭代器，并使用 hasNext 方法，那么你的总最坏情况运行时间将大于 O（n）。阿普罗昔酯公式将是一个常数加 n，其中 n 是 if 条件。迭代器需要恒定的时间来返回对象，这与 for 循环不同。

Answer 3

因此，假设 m 和 n 是两个列表，则总运行时间为 n+1m+2m+...+（n-n+1）m。