猿问

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

对于这段代码片段的 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)?


扬帆大鱼
浏览 241回答 2
2回答

青春有我

list大约有n^2/2项[*],所以查找list.contains(i*j)是O(n^2)不是O(n)*:少一些,因为没有添加重复项,但我想足以算作&nbsp;n^2

千万里不及你

list.contains(i*j)发生在O(n^2) 中,因为 i 和 j 依赖于 n(如果使用线性搜索)。基本上它将是 O(n) 嵌套的 2 个循环和嵌套循环内的 O(n^2) 操作,因此O(n^4).
随时随地看视频慕课网APP

相关分类

Java
我要回答