3个嵌套循环的时间复杂度计算

debugcn 发表于 Dev

测试假人

我正在尝试提高算法技能。我有一个非常简单的代码。

问：查找等于0的所有三元组（非重复）。

我认为与嵌套循环（n ^ 3）无关，时间复杂度为O（nlogn）。我的理由是：可以这样说

numslength =3。然后代码运行1次。{-1,0,-1}。numslength =3。然后代码运行1次。{-1,0,1,2}然后代码运行3次。-1,0,1，01,0,2，-1,1,2。

类似地，当length为0时，5代码运行6次[] [] [] [] [] []，而长度为7，则运行9次。

因此，似乎要考虑的三元组的数量随3(n-2)位置增加3<=n。因此，时间复杂度是n因为3n-6〜n。

但是因为我有Arrays.sort时间，复杂性变得了O(nlogn)。

我在俯视什么？

int[] nums = { -1, 0, 1, 2, -1, -4};
List<List<Integer>> test = new ArrayList<List<Integer>>();
nums = new int[] { -1, 0, 1};
Arrays.sort(nums);
HashSet<String> duplicates = new HashSet<String> ();

for (int i = 0 ; i < nums.length - 2 ; i++) { //i->0 - 3
    for (int j = i + 1; j < nums.length - 1; j++) { // j -> 1-4
        for (int k = j + 1; k < nums.length; k++) { //k ->2-5

            String sInt = nums[i] + "" + nums[j] + "" + nums[k];

            if ((nums[i] + nums[j] + nums[k]) == 0 && !duplicates.contains(sInt)) {
                ArrayList<Integer> t = new ArrayList<Integer> ();
                t.add(nums[i]);
                t.add(nums[j]);
                t.add(nums[k]);
                test.add(t);
            }

            duplicates.add(sInt);
        }
    }
}

return test;

用户名

有n*(n-1)(n-2)/6三胞胎，并且代码检查每一个。时间复杂度为O(n^3)。我看不出Arrays.sort()这里有什么意义。

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。