为什么带有 list.add 的嵌套循环的时间复杂度为 O(n^4)？

Question

对于这段代码片段的 Big O 时间复杂度，我遇到了这个问题：保证以下代码的时间复杂度为 O(n^4)。ArrayList<Integer> list = new ArrayList<Integer>();for(int i = n; i>=1; i--)           //n     for(int j = 1; j<=i; j++)       //n             if(!list.contains(i*j))     //n?                list.add(i*j);          //1?我的问题：为什么是 O(n^4) 而不是 O(n^3)？

Answer 1

list大约有n^2/2项[*]，所以查找list.contains(i*j)是O(n^2)不是O(n)

*：少一些，因为没有添加重复项，但我想足以算作 n^2

Answer 2

list.contains(i*j)发生在O(n^2) 中，因为 i 和 j 依赖于 n（如果使用线性搜索）。基本上它将是 O(n) 嵌套的 2 个循环和嵌套循环内的 O(n^2) 操作，因此O(n^4).