java - List に X と F(X) が含まれているかどうかを判断する Big-O ランタイム

Question

次の方法でBig Oが何であるかを理解しようとしています。

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

contains メソッドが O(n) であり、そのような for ループも O(n) であることを知っています。このメソッドの合計は O(n * n) になりますか?

Answer 1

がO（n）であると仮定するとList.contains、そうです、アルゴリズム全体はO（n ^ 2）です。

Answer 2

したがって、m と n が 2 つのリストであると仮定すると、合計実行時間は n+1m+2m+...+(n-n+1)m になります。

Answer 3

しかし、リストで反復子を使用し、hasNext メソッドを使用すると、最悪の場合の合計実行時間は O(n) になります。近似式は、定数に n を加えたものになります。ここで、n は if 条件です。forループとは異なり、反復子はオブジェクトを返すのに一定の時間がかかります。