我的嵌套循环的时间复杂度是多少？应该是 O(n) 还是 O(n^2)

Question

嘿，我在互联网上使用了 2 个免费的 Big O 检查器，它们都告诉我我的代码是 O(n^2)，但我确信它必须只是 O(n)。

for (int k = 0; k < 8; k++) {
        num = hwexamples[k];
        n = Integer.parseInt(num);
        int[] room = new int[n];
        for (int j = 0; j < n; j++) {
            room[j] = i;
            i = rndm.nextInt(365);
        }
        System.out.println(duplicatecheck(room));
    }

由于外层循环被限制为 8 次迭代，所以它不能是 n^2 对吗？我有什么遗漏的吗？

有关更多上下文，这是我调用的方法：

public static boolean duplicatecheck (int[] room) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < room.length; i++) {
            map.put(room[i], i);
        }
        for (int i = 0; i < room.length; i++) {
            int target = room[i];
            if (map.containsKey(target) && map.get(target) != i) {
                return true;
            }
        }
        return false;
    }

我期望得到 O(n)。我应该怎样做才能让代码更有效率？

Answer 1

第一段代码并不是以 𝑛 的值开始的，因此用 𝑛 来谈论它的时间复杂度是没有意义的。这段代码旨在创建八个随机输入并用它们调用

duplicatecheck

。

它是不完整的，因为它缺少

i

的声明，并且在给它一个值之前读取它的值。如果内部循环有这样的语句，那就更有意义了：

room[j] = rndm.nextInt(365);

此外，

hwexamples

未定义。

看

duplicatecheck

的时间复杂度似乎更合理，它的时间复杂度确实是O(𝑛)，其中𝑛是

room

数组的大小。

如果你真的想要第一段代码的时间复杂度，那么要意识到输入不是𝑛，而是

hwexamples

。假设数组有 8 个条目，复杂度为 O(sum(hwexamples))。